好贷网好贷款

HDOJ 3488 - Tour 有向图分割成若干哈密顿回路(二分图的最小权匹配,最小费用最大流)...

发布时间:2016-12-5 4:34:24 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDOJ 3488 - Tour 有向图分割成若干哈密顿回路(二分图的最小权匹配,最小费用最大流)...",主要涉及到HDOJ 3488 - Tour 有向图分割成若干哈密顿回路(二分图的最小权匹配,最小费用最大流)...方面的内容,对于HDOJ 3488 - Tour 有向图分割成若干哈密顿回路(二分图的最小权匹配,最小费用最大流)...感兴趣的同学可以参考一下。

                   题意:                             给一个有向图,问把所有的点都放在环中(可能不止一个)..最小代价是多少(做边的最小权值之和)                    题解:                            我没接触过这种模型..看了这个图才反应过来的:  左图可以看做是1,2成环,3,4,5成环。(source)                           把每个点拆成两个点,左边的点代表其出度点,右边的点代表其入度点...左边往右边的有向边代表两点间有边...问题转化成了求二分图的最小权匹配..用KM或者最小费用最大流解决... Program: #include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #include<math.h> #include<queue> #define MAXN 1005 #define MAXM 500005 #define oo 1000000007 #define ll long long using namespace std; struct MCMF { struct node { int x,y,c,v,next; }line[MAXM]; int Lnum,_next[MAXN],pre[MAXN],dis[MAXN],flow,cost; bool inqueue[MAXN]; void initial(int n) { Lnum=-1; for (int i=0;i<=n;i++) _next[i]=-1; } void addline(int x,int y,int c,int v) { line[++Lnum].next=_next[x],_next[x]=Lnum; line[Lnum].x=x,line[Lnum].y=y,line[Lnum].c=c,line[Lnum].v=v; line[++Lnum].next=_next[y],_next[y]=Lnum; line[Lnum].x=y,line[Lnum].y=x,line[Lnum].c=0,line[Lnum].v=-v; } bool SPFA(int s,int e) { int x,k,y; queue<int> Q; while (!Q.empty()) Q.pop(); memset(dis,0x7f,sizeof(dis)); memset(inqueue,false,sizeof(inqueue)); Q.push(s); dis[s]=0,pre[s]=-1; while (!Q.empty()) { x=Q.front(),Q.pop(),inqueue[x]=false; for (k=_next[x];k!=-1;k=line[k].next) if (line[k].c) { y=line[k].y; if (dis[y]>dis[x]+line[k].v) { dis[y]=dis[x]+line[k].v; pre[y]=k; if (!inqueue[y]) { inqueue[y]=true; Q.push(y); } } } } if (dis[e]>oo) return false; flow=oo,cost=0; for (k=pre[e];k!=-1;k=pre[line[k].x]) flow=min(flow,line[k].c),cost+=line[k].v; cost*=flow; for (k=pre[e];k!=-1;k=pre[line[k].x]) line[k].c-=flow,line[k^1].c+=flow; return true; } int MinCostMaxFlow(int s,int e) { int Aflow=0,Acost=0; while (SPFA(s,e)) { Aflow+=flow; Acost+=cost; } return Acost; } }T; int main() { int cases,i,x,y,d,n,m,s,e; scanf("%d",&cases); while (cases--) { scanf("%d%d",&n,&m); s=n<<2,e=s+1,T.initial(e); for (i=1;i<=n;i++) T.addline(s,i<<1,1,0),T.addline(i<<1|1,e,1,0); while (m--) { scanf("%d%d%d",&x,&y,&d); T.addline(x<<1,y<<1|1,1,d); } printf("%d\n",T.MinCostMaxFlow(s,e)); } return 0; }

上一篇:ARM汇编语言
下一篇:Spring AOP 实现原理与 CGLIB 应用

相关文章

相关评论