無向圖的最小費用流，建圖時可以分別加入兩條邊(u,v,w,c),(v,u,w,c)，即當做兩條有向邊。 建立一個超級源點和超級匯點，容量為2，其余邊容量為1，剩下的就是最小費用流的求解過程了。
  POJ 2135
#include<iostream>
using namespace std;
struct edge
{
int u,v,next,f,w;
}e[40010];
int n,m;
int mincost=0;
int p[2000];
int num=0;
int head[2000];
int s,t;
void add(int s,int t,int w,int c)
{
e[num].f=c;
e[num].next=head[s];
head[s]=num;
e[num].u=s;
e[num].v=t;
e[num++].w=w;
return ;
}
void addedge(int s,int t,int w,int c)
{
add(s,t,w,c);
add(t,s,-w,0);
return ;
}
bool spfa()
{
int i,j;
int Q[2000],front(0),tail(0);
int d[2000];
bool ok[2000];
memset(ok,0,sizeof(ok));
for(i=0;i<=n+2;i++)
{
d[i]=INT_MAX;
}
d[s]=0;
ok[s]=1;
p[s]=-1;
Q[++tail]=s;
while(tail!=front)
{
i=Q[++front];
ok[i]=0;
for(j=head[i];j!=-1;j=e[j].next)
{
if(e[j].f>0&&d[i]+e[j].w<d[e[j].v])
{
d[e[j].v]=d[i]+e[j].w;
p[e[j].v]=j;
if(!ok[e[j].v])
{
Q[++tail]=e[j].v;
ok[e[j].v]=1;
}
}
}
}
if(d[t]<INT_MAX)
return 1;
else return 0;
}
int solve()
{
int i;
int minflow=INT_MAX;
for(i=p[t];i!=-1;i=p[e[i].u])
{
if(minflow>e[i].f)
minflow=e[i].f;
}
for(i=p[t];i!=-1;i=p[e[i].u])
{
e[i].f-=minflow;
e[i^1].f+=minflow;
mincost+=e[i].w*minflow;
}
return 0;
}
int main()
{
scanf("%d%d",&n,&m);
int i;
int a,b,c;
memset(head,-1,sizeof(head));
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
addedge(a,b,c,1);
addedge(b,a,c,1);
}
s=0;
t=n+1;
addedge(s,1,0,2);
addedge(n,t,0,2);
while(spfa())
{
solve();
}
printf("%d\n",mincost);
system("pause");
return 0;
}
|