程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 2135 (基礎費用流)

poj 2135 (基礎費用流)

編輯:C++入門知識

題意:從1到n再到1,每條邊只能走一次,求最短距離。

建圖:每條邊只能走一次就是流量是1,添加源點與1相連,容量為2,費用為0,n與匯點相連容量為2,費用為0;

求增廣路用SPFA最短路求,,

 


 

#include<stdio.h>
#include<queue>
#include<string.h>
const int N=1100;
const int inf=0x3fffffff;
using namespace std;
int cost[N],start,end,n,head[N],num,pre[N],vis[N];
struct edge
{
	int st,ed,cp,flow,next;
}e[N*N];
void addedge(int x,int y,int c,int w)
{
	e[num].st=x;e[num].ed=y;e[num].cp=c; e[num].flow=w;e[num].next=head[x];head[x]=num++;
	e[num].st=y;e[num].ed=x;e[num].cp=-c;e[num].flow=0;e[num].next=head[y];head[y]=num++;
}
int SPFA()
{
	int i,u,v;
	queue<int>Q;
	for(i=start;i<=end;i++)
	{cost[i]=inf;vis[i]=0;pre[i]=-1;}
	cost[start]=0;vis[start]=1;
	Q.push(start);	
	while(!Q.empty())
	{
		u=Q.front();
		Q.pop();vis[u]=0;
		for(i=head[u];i!=-1;i=e[i].next)
		{
			v=e[i].ed;
			if(e[i].flow>0&&cost[v]>cost[u]+e[i].cp)
			{
				pre[v]=i;
				cost[v]=cost[u]+e[i].cp;
				if(vis[v]==0)
				{
					vis[v]=1;
					Q.push(v);
				}
			}
		}
	}
	if(pre[end]==-1)
		return 0;
	return 1;
}
int mincost()
{
	int MINcost=0,maxflow=0,i,minflow;
	while(SPFA())
	{
		minflow=inf;
		for(i=pre[end];i!=-1;i=pre[e[i].st])
			if(minflow>e[i].flow)
				minflow=e[i].flow;
			maxflow+=minflow;
		for(i=pre[end];i!=-1;i=pre[e[i].st])
		{
			e[i].flow-=minflow;
			e[i^1].flow+=minflow;
			MINcost+=e[i].cp;
		}			
	}
	return MINcost;
}
int main()
{
	int i,x,y,c,m;
	while(scanf("%d%d",&n,&m)!=-1)
	{
		start=0;end=n+1;num=0;
		memset(head,-1,sizeof(head));
		for(i=0;i<m;i++)
		{
			scanf("%d%d%d",&x,&y,&c);
			addedge(x,y,c,1);
			addedge(y,x,c,1);
		}
		addedge(start,1,0,2);
		addedge(n,end,0,2);
		printf("%d\n",mincost());
	}
	return 0;
}

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved