题目：
Sample Input
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
Sample Output
Infinite
Infinite
3
1
题意：
给定一个有向图，每条边都有一个权值。每次你可以选择一个结点v和一个整数d,把所有以v为终点的边的权值减小d,把所有以v为起点的边的权值增加d,最后让所有边的权值的最小值大于零且尽量大。
分析：
因为不同的操作互不影响，因此可以按任意顺序实施这些操作。另外，对于同一个点的多次操作可以合并，因此可以令sum(u)为作用于结点u之上的所有d之和。这样，本题的目标就是确定所有的sum(u),使得操作之后所有边权的最小值尽量大。
“最小值最大”又让我们想到使用二分答案的方法。二分答案x之后，问题转化为是否可以让操作完毕后每条边的权值均不小于x。对于边a->b，不难发现操作完毕后它的权值为w(a,b)+sum(a)-sum(b),因此每条边a->b都可以列出一个不等式w(a,b）+sum(a)-sum(b)>=x,移项得sum(b)-sum(a)<=w(a,b)-x。这样，我们实际得到一个差分约束系统。
差分约束系统是指一个不等式组，每个不等式形如xj-xi<=bk,这里的bk是一些事先已知的常数。这个不等式类似于最短路中的不等式d[v]<=d[u]+w(u,v),我们可以用最短路算法求解：对于约束条件xj-xi<=bk,新建一条边i->j，（根据最短路性质可以证明在图无负环的情况下这个不等式是成立的）权值为bk。如果图中有负权环，则差分约束系统无解。
代码如下：
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxn 510
#define Maxm 4010
#define INF 0xfffffff int n,m;
int first[Maxn],dis[Maxn],cnt[Maxn];
bool bq[Maxn],inq[Maxn]; struct node
{
int x,y,c,cc,next;
}t[Maxm];int len; int mymax(int x,int y) {return x>y?x:y;} void ins(int x,int y,int cc)
{
t[++len].x=x;t[len].y=y;t[len].cc=cc;
t[len].next=first[x];first[x]=len;
} queue<int > q; bool spfa(int s)
{
memset(inq,,sizeof(inq));
memset(dis,,sizeof(dis));
memset(cnt,,sizeof(cnt));
while(!q.empty()) q.pop();
dis[s]=;inq[s]=;q.push(s);
while(!q.empty())
{
int x=q.front();q.pop();inq[x]=;
for(int i=first[x];i;i=t[i].next)
{
int y=t[i].y;
if(dis[y]>dis[x]+t[i].c)
{
dis[y]=dis[x]+t[i].c;
if(!inq[y])
{
q.push(y);
inq[y]=;
if(++cnt[y]>n+) return ;
}
}
}
}
return ;
} bool check(int x)
{
memset(bq,,sizeof(bq));
for(int i=;i<=len-n;i++) t[i].c=t[i].cc-x;
if(spfa(n+)) return ;
/*for(int i=1;i<=n+1;i++) if(!bq[i])
{
if(spfa(i)) return 0;
}*/
return ;
} void ffind(int l,int r)
{
while(l<r)
{
int mid=(l+r+)>>;
if(check(mid)) l=mid;
else r=mid-;
}
printf("%d\n",l);
} int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(first,,sizeof(first));
int mx=-INF;len=;
for(int i=;i<=m;i++)
{
int x,y,cc;
scanf("%d%d%d",&x,&y,&cc);
ins(x,y,cc);
mx=mymax(cc,mx);
}
for(int i=;i<=n;i++)
{
ins(n+,i,);t[len].c=;
}
if(check(mx+)) {printf("Infinite\n");continue;}
if(!check()) {printf("No Solution\n");continue;}
ffind(,mx);
}
return ;
}
[UVA11478]
2016-04-10 15:33:20