书海扬帆的博客

本题运用图论中的差分约束算法即可解决。差分约束需要连一些表示变量间大小关系的边,然后运用SPFA算法求解。

我们把顶点0作为“超级源点”,在主函数的开始首先执行下面一段代码。

1
for(int i=1;i<=n;i++) addEdge(n+1,i,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
67
68
69
70
71
72
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=100100,maxm=500500;
struct Node
{
int v,c;
Node *next;
}*h[maxn],pool[maxm];
int tot=0;
int num[maxn];
int q[maxn],head=1,tail=1,vis[maxn],dis[maxm];
void addEdge(int u, int v, int c)
{
Node *p=&pool[++tot];
p->v=v; p->c=c; p->next=h[u]; h[u]=p;
}
int n,m,k,root;
int spfa()
{
root=n+1;
q[tail]=root;
tail++;
vis[root]=1;
for(int i=0;i<=n+1;i++) dis[i]=0x3f;
dis[root]=0;
while(head<tail)
{
if(tail>maxn) return 0;
k=q[head];
for(Node *p=h[k];p;p=p->next)
{
if(dis[p->v]>dis[k]+p->c)
{
dis[p->v]=dis[k]+p->c;
if(vis[p->v]==0)
{
q[tail]=p->v;
tail++;
vis[p->v]=1;
}
}
}
vis[q[head]]=0;
head++;
}
return 1;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) addEdge(n+1,i,0);
for(int i=1;i<=m;i++){
int u,v,c,res;
scanf("%d",&res);
if(res==1){
scanf("%d%d%d",&u,&v,&c);
addEdge(u,v,c);
}
else if(res==2){
scanf("%d%d%d",&u,&v,&c);
addEdge(v,u,-c);
}
else if(res==3){
scanf("%d%d",&u,&v);
addEdge(u,v,0);
}
}
if(spfa()==1) printf("Yes");
else printf("No");
return 0;
}



本站使用 Material-X 作为主题 , 总访问量为 次 。
载入天数...载入时分秒... 字数统计:730.1k