加加减减(pands.pas/c/cpp)
【题目背景】
话说zyk又双叒叕在A图论的题目了！！！
【问题描述】
zyk手里有若干幅有向图，每条边有个权值。你可以在这幅图上操作若干次（也是醉了），每次可以选择一个节点u和一个整数d，把以u为起点的边的权值增加d，把以u为终点的边的权值减小d（难怪叫加加减减）。然而，zyk却想让所有边权的最小值为正且尽量大。
【输入文件】
输入包含若干组数据。每组数据第一行为两个整数n和m（n≤500，m≤700），即点和边的个数。以下m行每行三个整数u，v，w，即一条起点为u，终点为v，权值为w的边（1≤u，v≤n，-10000≤w≤10000）。
【输出文件】
对于每组数据，输出边权最小值的最大值。如果无法让所有边权都为正，输出“No Solution”；如果最小边权的最大值可以任意大，输出“Infinite”。
【输入样例】
2 1
1 2 10
2 1
1 2 -10
3 3
1 2 4
2 3 2
3 1 5
4 5
2 3 4
4 2 5
3 4 2
3 1 0
1 2 -1
【输出样例】
Infinite
Infinite
3
1
首先，我们应该注意到，结果与操作的顺序是无关的。所以，对于同一个节点，对于它的多次操作，可以合并。那么我们令sum(k)为作用在u上的所有权值之和。这样，我们的目标就是求出min(sum(i))(i=1,n)。而题目中最小值最大又使我们自然而然想到二分。枚举一个low，使问题变成操作完后能否使每条边权值不小于low。对于边a→b，在操作完后它的权值为w(a,b)+sum(a)-sum(b)。因此对于每条边，都可以列出一个不等式w(a,b)+sum(a)-sum(b)≥low，移项得sum(b)<=sum(a)+w(a,b)-x。显然，我们得到一个查分约束系统。并且这个差分约数系统转化为图论的话应该是众多个里面挑最小的。所以应转为最短路问题。所以更新的那句话就变为if (sum(b)>sum(a)+w(a,b)-x) ......。当然，还有特殊情况，即No Solution和Infinite。
对于Infinite的情况：
判断spfa(最大边权+1)是不是真值。
因为当low=最大边权时，所有边的边权都得到了增加，说明一个问题——按照这样的操作继续下去，最小边权肯定还是增加的，所以可以一直这样操作下去，最小边权也就无穷大了。
对于No Sulotion的情况：
判断spfa(1)是不是假值。
由于最小边权要大于0，且为整数，所以至少唯一。如果1都达不到，就无解了。但是怎么判断这个查分约束系统无解？可以画一个图，例如：
x1<=x4,x2<=x1+3,x3<=x1-1,x3<=x2-2,x4<=x3-2（见下）
整理后发现部分不等式矛盾：x1<=x4+0,x3<=x1-1,x4<=x3-2（见下）
实质就是出现了负权回路。或者就根据这个例子分析，又前两个不等式得x3<=x4-1。而后又出现x3>=x4+2。这两个不等式没有解集。只有最后一个不等式至少变为x4<=x3+1时才有集解（即x3>=x4-1,得x3=x4-1），此时，三条边权值和为0-1+1=0。而刚才权值和为0-1-2=-3<0，可见，如果不等式组无解，则spfa(low)=false。
如果并不是特殊情况——直接二分得出答案。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int maxn=505,maxe=705,maxv=505; 6 int n,m,h,t,son[maxe],w[maxe],nxt[maxe],lnk[maxn],tot; 7 int q[maxv],d[maxn],ins[maxn]; 8 bool v[maxn]; 9 inline int read(){10int x=0,f=1; char ch=getchar();11while (ch<'0'||ch>'9'){if (ch=='-') f=-f; ch=getchar();}12while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();13return x*f;14 }15 void add(int x,int y,int z){16nxt[++tot]=lnk[x],son[tot]=y,w[tot]=z,lnk[x]=tot;17 }18 bool spfa(int low){19memset(q,0,sizeof q);20memset(d,63,sizeof d);21memset(v,0,sizeof v);22memset(ins,0,sizeof ins);23h=0,t=0;24for (int i=1; i<=n; i++) q[++t]=i,d[i]=0,v[i]=1,ins[i]++;25while (h!=t){26 h=(h+1)%maxv; v[q[h]]=0;27 for (int j=lnk[q[h]]; j; j=nxt[j]){28 if (d[son[j]]>d[q[h]]+w[j]-low){29 d[son[j]]=d[q[h]]+w[j]-low;30 if (!v[son[j]]){31 v[son[j]]=1,t=(t+1)%maxv,q[t]=son[j],ins[son[j]]++;32 if (ins[son[j]]>n) return 0;33 if (d[q[t]]<d[q[(h+1)%maxv]]) swap(q[t],q[(h+1)%maxv]);34 }35 }36 }37}38return 1;39 }40 int main(){41while (~scanf("%d%d",&n,&m)){42 int L=1,R=-(1<<30),ans=0;43 tot=0;44 memset(lnk,0,sizeof lnk);45 memset(nxt,0,sizeof nxt);46 for (int i=1; i<=m; i++){47 int x=read(),y=read(),z=read();48 add(x,y,z),R=max(R,z);49 }50 if (spfa(R+1)){51 puts("Infinite"); continue;52 }else53 if (!spfa(L)){54 puts("No Solution"); continue;55 }56 while (L<=R){57 int mid=(L+R)>>1;58 if (spfa(mid)) ans=mid,L=mid+1; else R=mid-1;59 }60 printf("%d\n",ans);61}62return 0;63 }
View Code
