http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=9
题目大意：
给定一个有向图，每条边都有一个权值，每次你可以选择一个结点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。如果图中有负权环，则差分约束系统无解。
PS:用超级源点的话2.7S，如果不用超级源点，把所有点加入队列那么2.1S。。。以后我还是不用超级源点吧。
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=500+10;
const int MAXM=2700+10;
const int INF=100000+10;
int head[MAXN],len,dis[MAXN],vis[MAXN],cnt[MAXN],n,m;
struct edge
{
int to,val,next;
}e[MAXM];
void add(int from,int to,int val)
{
e[len].to=to;
e[len].val=val;
e[len].next=head[from];
head[from]=len++;
}
bool spfa()
{
memset(vis, 0, sizeof(vis));
memset(cnt, 0, sizeof(cnt));
queue<int> q;
for(int i = 0; i <=n; i++) { dis[i] = 0;q.push(i); }
while(!q.empty())
{
int cur=q.front();
q.pop();
vis[cur]=false;
for(int i=head[cur];i!=-1;i=e[i].next)
{
int id=e[i].to;
if(dis[id] > dis[cur]+e[i].val)
{
dis[id]=dis[cur]+e[i].val;
if(!vis[id])
{
if(++cnt[id] >n)
return false;
vis[id]=true;
q.push(id);
}
}
}
}
return true;
}
bool change(int x)
{
for(int k=1;k<=n;k++)
for(int i=head[k];i!=-1;i=e[i].next)
e[i].val-=x;
bool ok=spfa();
for(int k=1;k<=n;k++)
for(int i=head[k];i!=-1;i=e[i].next)
e[i].val+=x;
return ok;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
memset(head,-1,sizeof(head));
len=0;
// for(int i=1;i<=n;i++)
// add(0,i,0);
int L=1,R=0;
for(int i=0;i<m;i++)
{
int from,to,val;
scanf("%d%d%d",&from,&to,&val);
add(from,to,val);
if(val > R) R=val;
}
if(change(R))
{
puts("Infinite");
continue;
}
else if(!change(L))
{
puts("No Solution");
continue;
}
int ans=L++;
while(L<R)
{
int mid=L+((R-L)>>1);
if(!change(mid))
R=mid;
else
{
L=mid+1;
ans=mid;
}
}
printf("%d\n",ans);
}
return 0;
}
超级源点。。。以后差分约束不用了- -
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=500+10;
const int MAXM=27000;
const int INF=100000+10;
int head[MAXN],len,dis[MAXN],vis[MAXN],cnt[MAXN],n,m;
struct edge
{
int to,val,next;
}e[MAXM];
void add(int from,int to,int val)
{
e[len].to=to;
e[len].val=val;
e[len].next=head[from];
head[from]=len++;
}
bool spfa()
{
for(int i=1;i<=n;i++)
{
vis[i]=false;
dis[i]=INF;
cnt[i]=0;
}
queue<int> q;
q.push(0);
cnt[0]++;
dis[0]=0;
vis[0]=true;
while(!q.empty())
{
int cur=q.front();
q.pop();
vis[cur]=false;
for(int i=head[cur];i!=-1;i=e[i].next)
{
int id=e[i].to;
if(dis[id] > dis[cur]+e[i].val)
{
dis[id]=dis[cur]+e[i].val;
if(!vis[id])
{
if(++cnt[id] >n)
return false;
vis[id]=true;
q.push(id);
}
}
}
}
return true;
}
bool change(int x)
{
for(int k=1;k<=n;k++)
for(int i=head[k];i!=-1;i=e[i].next)
e[i].val-=x;
bool ok=spfa();
for(int k=1;k<=n;k++)
for(int i=head[k];i!=-1;i=e[i].next)
e[i].val+=x;
return ok;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
memset(head,-1,sizeof(head));
len=0;
for(int i=1;i<=n;i++)
add(0,i,0);
int L=1,R=0;
for(int i=0;i<m;i++)
{
int from,to,val;
scanf("%d%d%d",&from,&to,&val);
add(from,to,val);
if(val > R) R=val;
}
if(change(R))
{
puts("Infinite");
continue;
}
else if(!change(L))
{
puts("No Solution");
continue;
}
int ans=L++;
while(L<R)
{
int mid=L+((R-L)>>1);
if(!change(mid))
R=mid;
else
{
L=mid+1;
ans=mid;
}
}
printf("%d\n",ans);
}
return 0;
}