P1938 P2648 赚钱

题意：求最长路

p1938

先点权转边权，然后求最长路，可能有负环，所以用spfa

求最长路的两个方法：

1、 将 d 数组初始化为 0，每次更新最大值

2、 所有边权取反后，求最短路（dij不能处理负边环，所以spfa）

p2648

在上一题的基础上，建出一个超级源点，然后给他和每个点连一条权值是 0 的边。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
//**p2648**
const int INF=0x3f3f3f3f;
const int MAX=300+10;
int d,p,c,f,ai,bi,ji,ki,ti,ans,low[MAX],cnt[MAX];
struct Edge{
	int to,next,c;
}edge[MAX*MAX];
int tot,head[MAX];
void init(){
	tot=0;
	mem(head,-1);
}
void addedge(int u,int v,int c){
	edge[tot].to=v;
	edge[tot].c=c;
	edge[tot].next=head[u];
	head[u]=tot++;
}
bool spfa(int s){
	queue<int>q;
	bool inq[MAX];//这里是要初始化的！
	mem(inq,0);
	low[s]=d; //起点是有值的，本题 
	q.push(s);
	while(!q.empty()){
		int u = q.front();
		q.pop();
		if(++cnt[u]>c) return false;
		inq[u]=0;
		for(int i=head[u];i!=-1;i=edge[i].next){
			int v=edge[i].to;
			int c=edge[i].c;
			if(low[v] < low[u] +c){
				low[v] = low[u] +c;
				if(!inq[v]){ 
					inq[v]=1;
					q.push(v);
				}
			}
		}
	}
	return true;
}
int main(){
	freopen("in","r",stdin);
	sf(d);sf(p);sf(c);sf(f);
	init();
	fi(i,0,p){
		sf(ai);sf(bi);
		addedge(ai,bi,d);
	}
	fi(i,0,f){
		sf(ji);sf(ki);sf(ti);
		addedge(ji,ki,d-ti);
	}
	fi(i,1,c+1)
		addedge(0,i,0);
	if(!spfa(0)){
		pfc("orz"); return 0;
	}
	fi(i,1,c+1){
		ans = max(ans,low[i]);
	}
	pf(ans);
	return 0;
}