题目描述
小K在MC里面建立很多很多的农场，总共n个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共m个），以下列三种形式描述：
- 农场a比农场b至少多种植了c个单位的作物，
- 农场a比农场b至多多种植了c个单位的作物，
- 农场a与农场b种植的作物数一样多。
但是，由于小K的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。
输入输出格式
输入格式：
第一行包括两个整数 n 和 m，分别表示农场数目和小 K 记忆中的信息数目。
接下来 m 行：
如果每行的第一个数是 1，接下来有 3 个整数 a,b,c，表示农场 a 比农场 b 至少多种植
了 c 个单位的作物。
如果每行的第一个数是 2，接下来有 3 个整数 a,b,c，表示农场 a 比农场 b 至多多种植
了 c 个单位的作物。如果每行的第一个数是 3，家下来有 2 个整数 a,b，表示农场 a 终止的
数量和 b 一样多。
输出格式：
如果存在某种情况与小 K 的记忆吻合，输出“Yes”，否则输出“No”。
输入输出样例
说明
对于 100% 的数据保证：1 ≤ n，m，a，b，c ≤ 10000。
思路：设d[i]表示第i个点的数值。
那么对于约束
1:d[a]-d[b]>=c
2:d[a]-d[b]<=c
3:d[a]=d[b]
让我们稍微变化一下式子
1:d[b]<=d[a]-c
2:d[a]<=d[b]+c
3:d[a]<=d[b]+0,d[b]<=d[a]+0
这不是和最短路中dist的定义很像吗？每个点的距离都小于等于能到他的点的距离+边权。
于是我们将其转化成一个最短路模型。
对于约束
1:我们连边(a,b,-c).
2:我们连边(b,a,c).
3:我们连边(a,b,0),(b,a,0)。
因为d[i]>=0，所以我们建一个起点s，向所有点连一条(s,i,0)的边。
然后d[s]显然=0.
我们发现这样子跑一个最短路就能确定每个点的d值啦
那什么时候是无解呢？当然是无法确定每个点的最短路的时候，也就是图中存在负权环。
我们建完图以后判断是否存在负权环就可以啦。
#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 100010 using namespace std; queue<int>que; int n,m,tot,flag; int dis[MAXN],vis[MAXN]; int to[MAXN],cap[MAXN],net[MAXN],head[MAXN]; void add(int u,int v,int w){ to[++tot]=v;cap[tot]=w;net[tot]=head[u];head[u]=tot; } void spfa(int x){ if(flag) return ; vis[x]=1; for(int i=head[x];i;i=net[i]) if(dis[to[i]]>dis[x]+cap[i]){ dis[to[i]]=dis[x]+cap[i]; if(vis[to[i]]){ flag=1;return ; } spfa(to[i]); } vis[x]=0; } int main(){ freopen("farm.in","r",stdin); freopen("farm.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int opt,x,y,z; scanf("%d",&opt); if(opt==1){ scanf("%d%d%d",&x,&y,&z); add(x,y,-z); } else if(opt==2){ scanf("%d%d%d",&x,&y,&z); add(y,x,z); } else if(opt==3){ scanf("%d%d",&x,&y); add(x,y,0); add(y,x,0); } } for(int i=1;i<=n;i++) add(0,i,0); memset(dis,0x7f,sizeof(dis)); dis[0]=0;spfa(0); if(flag) printf("No"); else printf("Yes"); } /* 3 3 3 1 2 1 1 3 1 2 2 3 2 */ /* 10 10 3 9 5 1 6 1 1 1 2 8 0 1 2 8 1 2 4 5 0 1 1 2 1 1 10 5 0 1 10 1 0 2 6 7 0 2 9 3 0 */