现在的位置: 首页 > 综合 > 正文

poj 2391

2013年09月06日 ⁄ 综合 ⁄ 共 2781字 ⁄ 字号 评论关闭

又是网络流的建模.二分枚举答案。做这道题时,感觉做过类似的,想都没想就用之前的那个思路做了,结果错的。之前的思路就是,先求出任意两点间的最短路径,然后通过当前枚举的限制,把两点间路径在这个限制内的两点直接i连一条双向边。建s,t,s点到所有点连一条有向边,所有点到t连一条有向边。但这思路是错的,因为虽然在建的图中,任何从s到t的一个流的路径中的相临两点是在限制中,但这些满足限制的边可能经过组合就会大于限制,那么通过这条路径的流肯定是不满足限制的,所以给出的限制在这种情况下就完全违背了限制的初衷,也就会得到错误的结果。任何一个牛要走的话,肯定是从一个点i运动到j(j可以为i),中间怎么走的不需要考虑。不管i,j中间的路径多复杂,肯定走的是最小花费路径,也就是求的最短路,因为每条边的容量和方向都是无限制的,所以流要从i到j,肯定一直可以走这条最短路。所以就可以抽象出一个新的二分图,左边是各点,右边也是各点,左边到右边的点如果两点间最短路径小于限制的话,就连一条容量无穷的有向边,因为它可以一直走。然后加s,t,s连向左边的点容量为每个点有的cow数。右边的所有点连向t,容量为点可容纳的cow数。个人感觉就是和匹配差不多,这样求最大流就是最终结果。刚开始还有一个错误的思路就是,认为一个点如果有牛,又有容量,就把牛直接放到这个点内,也就是直接确定了一些流的方案,给一些边赋了流值。但是虽然牛所在的点有容量,他还是可以移动的,而可能就是最最短花费时间的方案。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxf=210*2;
const int maxp=200000;
const int  inf=1<<20;
const long long inf2=1152921504606000000;
struct Edge
{
	int from,to,flow,cap,next;
};
Edge e[maxp];	
int f,p,s,t,tot,head[maxf],maxflow,cur[maxf],d[maxf],amount,tn[maxf],tc[maxf];
long long tcost[maxf],path[maxf][maxf],high,low,mid,tem;
void addedge(int from,int to,int cap)
{
    e[tot].from=from;e[tot].to=to;e[tot].flow=0;e[tot].cap=cap;
    e[tot].next=head[from];head[from]=tot;tot++;
    e[tot].from=to;e[tot].to=from;e[tot].flow=0;e[tot].cap=0;
    e[tot].next=head[to];head[to]=tot;tot++;
}
void floyd()
{
	int i,j,k;
	for(k=1;k<=f;k++)
	{
		for(i=1;i<=f;i++)
		{
			for(j=i+1;j<=f;j++)
			{
				path[i][j]=path[j][i]=min(path[i][j],path[i][k]+path[k][j]);
			}
		}
	}
}
void build(long long limit)
{
	memset(head,-1,sizeof(head));
	tot=0;
	int x,y,i,j;
	for(i=1;i<=f;i++)
	{
		x=i*2-1;y=i*2;
		addedge(s,x,tn[i]);
		addedge(y,t,tc[i]);
	}
	for(i=1;i<=f;i++)
	{
		for(j=1;j<=f;j++)
		{
			if(path[i][j]<=limit) addedge(i*2-1,j*2,inf);
		}
	}
}
bool bfs()
{
	queue<int> q;
	memset(d,-1,sizeof(d));
	d[s]=0;
	q.push(s);
	while(!q.empty())
	{
		int x=q.front();q.pop();
		for(int i=head[x];i!=-1;i=e[i].next)
		{
			if(d[e[i].to]==-1&&(e[i].cap-e[i].flow)>0)
			{
				tcost[e[i].to]=tcost[x]+path[x][e[i].to];
				d[e[i].to]=d[x]+1;
				q.push(e[i].to);
			}
		}
	}
	if(d[t]==-1) return false;
	else return true;
}
int dfs(int x,int a)
{
	if(x==t||a==0) return a;
	int tf,flow=0;
	for(int& i=cur[x];i!=-1;i=e[i].next)
	{
		if(d[x]+1==d[e[i].to]&&(tf=dfs(e[i].to,min(a,e[i].cap-e[i].flow)))>0)
		{
			e[i].flow+=tf;
			e[i^1].flow-=tf;
			flow+=tf;
			a-=tf;
			if(a==0) break;
		}
	}
	return flow;
}
bool dinic()
{
	long long flow=0;
	while(bfs())
	{
		memcpy(cur,head,(f*2+2)*sizeof(int));
		flow+=dfs(s,inf);
	}
	if(flow<amount) return false;
	else return true;
}
long long solve()
{
	low=0;high=inf2;
	while(high-low>0)
	{
		mid=low+(high-low)/2;
		build(mid);
		if(dinic()) high=mid;
		else low=mid+1;
	}
	return high;
}
int main()
{
	//freopen("in.txt","r",stdin);
	while(cin>>f>>p)
	{
		tot=0;s=0;t=2*f+1;amount=0;
		int i,j;
		for(i=1;i<=f;i++)
		{
			for(j=1;j<=f;j++)
			{
				path[i][j]=(i==j)?0:inf2;
			}
		}
		for(i=1;i<=f;i++)
		{
			scanf("%d%d",&tn[i],&tc[i]);
			amount+=tn[i];
		}
		int u,v,co;
		for(i=1;i<=p;i++)
		{
			scanf("%d%d%d",&u,&v,&co);
			if(path[u][v]>co) path[u][v]=path[v][u]=co;
		}
		tem=-1;
		floyd();
		long long ou=solve();
		printf("%I64d\n",ou==inf2?-1:ou);
	}
	return 0;
}

抱歉!评论已关闭.