本文主要是介绍hdu 3435 A new Graph Game(最小费用最大流)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://acm.hdu.edu.cn/showproblem.php?pid=3435
题意： 一个无向图（or 有向图）， 每一个点都必须属于一个圈， 并且只能属于一个圈， 求满足要求的最小费用。
比如：
1 2 5
2 3 5
3 1 10
3 4 12
4 1 8
4 6 11
5 4 7
5 6 9
6 5 4
there are two cycles, (1->2->3->1) and (6->5->4->6) whose length is 20 + 22 = 42
像这样构成圈并且每个点只能属于一个圈的题， 可以转化成2 分图， 每个点只能属于一个圈， 那么出度和入度必定为1 ， 那么把一个点拆开i, i`， i控制入读， i` 控制出度， 流量只能为1 。 那么对于原来图中有的边 可以 i - > j`, j - > i`;连起来构图， 然后建立超级远点s，超级汇点t，s - > i ， i` - > t ; 然后求最小费用流。。这样就保证了每个点只能属于一个圈， 因为入读 == 出度 == 1 ；这类也问题可以 做为判断性问题出。
关键是拆点建图，把每个顶点拆成i和i+n。附加一个源点S和汇点T。
S与1~n建边，容量为1，花费为0；
n+1~n*2与T建边，容量为1，花费为0。
若ab右边，a与b+n建边，容量为1，花费为c,b与a+n建边，容量为1，花费为c。
求最小费用流。
最后判断时，因为每个点都存在某个双连通分量中，那么每个点（1~n）的总流量为0。若某个点的总流量不为0，输出NO。
否则，输出最小费用流。
#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
#define inf 0x3f3f3f3fconst int maxn = 55555;
using namespace std;queue<int>que;
struct node
{int u,v,f,c,next;
}edge[maxn];int head[maxn];
bool vis[maxn];
int dis[maxn];
int pre[maxn];
int n,m,s,t,cnt;void add(int u,int v,int f,int c)
{edge[cnt] = (struct node){u,v,f,c,head[u]};head[u] = cnt++;edge[cnt] = (struct node){v,u,0,-c,head[v]};head[v] = cnt++;
}bool spfa()
{int j;while(!que.empty()) que.pop();memset(vis,false,sizeof(vis));memset(dis,0x3f,sizeof(dis));memset(pre,-1,sizeof(pre));vis[s]=true;dis[s]=0;que.push(s);while(!que.empty()){int u=que.front();que.pop();vis[u]=false;for(j=head[u]; j!=-1; j=edge[j].next){int v=edge[j].v;if(edge[j].f&&dis[u]+edge[j].c<dis[v]){dis[v]=dis[u]+edge[j].c;pre[v]=j;if(!vis[v]){vis[v]=true;que.push(v);}}}}return dis[t]!=inf;
}int mincost()
{int ret=0,u;while(spfa()){u=pre[t];ret+=dis[t];while(u!=-1){edge[u].f--;edge[u^1].f++;u=pre[edge[u].u];}}return ret;
}
int main()
{int test;scanf("%d",&test);for(int item = 1; item <= test; item++){cnt = 0;memset(head,-1,sizeof(head));scanf("%d%d",&n,&m);s=0;t=2*n+1;int a,b,c;for(int i=1; i<=m; i++){scanf("%d%d%d",&a,&b,&c);add(a,b+n,1,c);add(b,a+n,1,c);}for(int i=1; i<=n; i++){add(s,i,1,0);add(i+n,t,1,0);}int ans=mincost();int j;for(j=head[s]; j!=-1; j=edge[j].next)if(edge[j].f!=0)break;if(j==-1) printf("Case %d: %d\n",item,ans);else printf("Case %d: NO\n",item);}return 0;
}
这篇关于hdu 3435 A new Graph Game(最小费用最大流)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
