tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

AOJ 2598: Website Tour

この記事は、AOJ-ICPC Advent Calendarの記事です。


強連結成分分解をする。それぞれの強連結成分には2パターンある。何度でも強連結成分内の好きな頂点にいけるやつと、1点しかなくてしかも自己ループすらないやつ。
後者は0-1、前者は好きな回数使えるナップサックをする。DAG上で。とはいっても、DAG要素は今見ている強連結成分に到達可能な強連結成分それぞれのmaxをとるで解消できる。

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int p[110];
int q[110];
int r[110];
vector<int>g[110];
int g2[110][110];
int UF[110];
int FIND(int a){
    if(UF[a]<0)return a;
    return UF[a]=FIND(UF[a]);
}
void UNION(int a,int b){
    a=FIND(a);b=FIND(b);if(a==b)return;UF[a]+=UF[b];UF[b]=a;
}
int dp[110][11000];
int jk[110];
int sz;
int top[110];
int rep[110];
int v[110];
int cnt;
void dfs(int a){
    v[a]=1;
    for(int i=0;i<sz;i++){
        if(i!=a&&g2[rep[a]][rep[i]]&&!v[i]){
            dfs(i);
        }
    }
    top[cnt--]=a;
}
int main(){
    int a,b,c;
    while(scanf("%d%d%d",&a,&b,&c),a){
        for(int i=0;i<a;i++)jk[i]=0;
        for(int i=0;i<a;i++){
            scanf("%d%d%d",p+i,q+i,r+i);
        }
        for(int i=0;i<a;i++)for(int j=0;j<a;j++)g2[i][j]=0;
        for(int i=0;i<a;i++)g2[i][i]=1;
        for(int i=0;i<a;i++)g[i].clear();
        for(int i=0;i<b;i++){
            int s,t;scanf("%d%d",&s,&t);s--;t--;
            if(s==t)jk[s]=1;
            g[s].push_back(t);
            g2[s][t]=1;
        }
        for(int k=0;k<a;k++)for(int i=0;i<a;i++)for(int j=0;j<a;j++){
            g2[i][j]|=(g2[i][k]&g2[k][j]);
        }
        for(int i=0;i<a;i++)UF[i]=-1;
        for(int i=0;i<a;i++)for(int j=i+1;j<a;j++){
            if(g2[i][j]&&g2[j][i])UNION(i,j);
        }
        sz=0;
        for(int i=0;i<a;i++){
            if(UF[i]<0){
                rep[sz++]=i;
            }
        }
        cnt=sz-1;
        for(int i=0;i<sz;i++){
            v[i]=0;
        }
        for(int i=0;i<sz;i++){
            if(v[i]==0){
                dfs(i);
            }
        }
        for(int i=0;i<sz;i++)for(int j=0;j<=c;j++)dp[i][j]=-999999999;
        for(int i=0;i<sz;i++)dp[i][0]=0;
        for(int i=0;i<sz;i++){
            for(int j=0;j<i;j++){
                if(g2[rep[top[j]]][rep[top[i]]]){
                    for(int k=0;k<=c;k++)dp[i][k]=max(dp[i][k],dp[j][k]);
                }
            }
            if(UF[rep[top[i]]]==-1&&jk[rep[top[i]]]==0){
                for(int j=c;j>=q[rep[top[i]]];j--){
                    dp[i][j]=max(dp[i][j],dp[i][j-q[rep[top[i]]]]+p[rep[top[i]]]);
                }
            }else{
                for(int j=0;j<a;j++){
                    if(FIND(j)==rep[top[i]]){
                        for(int k=0;k<q[j];k++){
                            deque<pair<int,int> >Q;
                            for(int l=k;l<=c;l+=q[j]){
                                while(Q.size()&&dp[i][l]-p[j]*(l/q[j])>=Q.back().second){
                                    Q.pop_back();
                                }
                                Q.push_back(make_pair(l,dp[i][l]-p[j]*(l/q[j])));
                                dp[i][l]=max(dp[i][l],Q.front().second+p[j]*(l/q[j]));
                                if(Q.front().first<=l-r[j]*q[j])Q.pop_front();
                            }
                        }
                    }
                }
            }
        //  printf("%d %d %d\n",rep[top[i]],UF[rep[top[i]]],jk[rep[top[i]]]);
    //      for(int j=0;j<=c;j++)printf("%d ",dp[i][j]);
//          printf("\n");
        }
        int ret=0;
        for(int i=0;i<sz;i++)for(int j=0;j<=c;j++)ret=max(ret,dp[i][j]);
        printf("%d\n",ret);
    }
}