题解 P1938 【[USACO09NOV]找工就业Job Hunt】

北海_Beihai · 2018-08-21 22:03:24 · 题解

拆点！！！

因为本题有点权(d)，所以把第i个点拆成i和i+c两个点，连一条边(i,i+c,d)（从i到i+c，费用为d，下同），把原来连到i的边还连到i，从i出发的点改为从i+c出发，然后对这2c个跑Floyd求最长路即可。（这里的“费用”指收入）

#include<cstdio>
#include<algorithm>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)    //宏简化循环
inline int read(){  //快读
    char c;
    while((c=getchar())<48||c>57);
    int ret=c-48;
    while((c=getchar())>47&&c<58) ret=ret*10+c-48;
    return ret;
}
int d,p,c,f,s,g[500][500];
int main(){
    scanf("%d%d%d%d%d",&d,&p,&c,&f,&s);
    int n=c*2;  //拆点后点的总数
    FOR(i,1,n) FOR(j,1,n) g[i][j]=-1e9; //负无穷大
    FOR(i,1,c) g[i][i+c]=d; //自己连到自己，即点权
    FOR(i,1,p) g[read()+c][read()]=0;   //路的费用为0
    FOR(i,1,f){
        int a=read(),b=read(),x=read();
        if(-x>g[a+c][b]) g[a+c][b]=-x;  //航线的费用为负数
    }
    FOR(k,1,n) FOR(i,1,n) FOR(j,1,n)    //Floyd最长路
        if(g[i][j]<g[i][k]+g[k][j]) g[i][j]=g[i][k]+g[k][j];
    int ans=-1e9;
    FOR(i,1,n) if(g[s][i]>ans) ans=g[s][i]; //找最大值
    printf("%d",ans);   //华丽的输出
    return 0;
}