UVA 11478-Halum差分制約

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=9
テーマ:
有向図を与えると、各エッジには重み値があり、ノードvと整数dを選択するたびに、vを終点とするすべてのエッジ重み値をd減少させ、vを起点とするすべてのエッジ重み値をd増加させ、最後にすべてのエッジ重み値を負でなく最大にすることができます.
考え方:
この問題を作るために前にいくつかの問題の差分制約をしました...
作者の考え方は巧みだ.
異なる動作は互いに影響を及ぼさないので、これらの動作を任意の順序で実施することができ、また、同じノードに対する複数回の動作も統合することができるので、sum(u)をノードuに作用するすべてのdの和とする.このように,本題の目標は,操作後のすべてのエッジ重み値の最小値ができるだけ大きくなるように,すべてのsum(u)を決定することである.
[最小値最大](Min Value Max)は、2分の1の答えを使用します.2分の1の答え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.7 S、スーパーソースポイントを使わないなら、すべてのポイントをキューに入れるなら2.1 S...これからはスーパーソースポイントは使わないでしょう.

#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
",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
",ans);
	}
	return 0;
}