首页 > 代码库 > hdu1853/ hdu 3488 有向图,取k个圈覆盖所有点一次//费用流
hdu1853/ hdu 3488 有向图,取k个圈覆盖所有点一次//费用流
哎╮(╯▽╰)╭,这是费用流基础题型,拆点,建二分图,跑最小费用最大流即可。若最大流为n,则说明是最大匹配为n,所有点都参与,每个点的入度和出度又是1,所以就是环。
弱菜还需努力!
#include<cstdio> #include<iostream> #include<queue> #include<cstring> using namespace std; const int inf=0x3f3f3f3f; int nume=0;int e[50000][4];int head[500]; int n,m; void inline adde(int i,int j,int c,int w) { e[nume][0]=j;e[nume][1]=head[i];head[i]=nume; e[nume][2]=c;e[nume++][3]=w; e[nume][0]=i;e[nume][1]=head[j];head[j]=nume; e[nume][2]=0;e[nume++][3]=-w; } int inq[500];int pre[500];int prv[500]; int d[500]; bool spfa(int &sum,int &sumflow) { for(int i=0;i<=2*n+2;i++) { inq[i]=0; d[i]=inf; } queue<int>q; q.push(0); inq[0]=1; d[0]=0; while(!q.empty()) { int cur=q.front(); q.pop(); inq[cur]=0; for(int i=head[cur];i!=-1;i=e[i][1]) { int v=e[i][0]; if(e[i][2]>0&&d[cur]+e[i][3]<d[v]) { d[v]=d[cur]+e[i][3]; pre[v]=i; prv[v]=cur; if(!inq[v]) { q.push(v); inq[v]=1; } } } } if(d[2*n+2]==inf)return 0; int cur=2*n+2;int minf=inf; while(cur!=0) { minf=e[pre[cur]][2]<minf?e[pre[cur]][2]:minf; cur=prv[cur]; } cur=2*n+2; while(cur!=0) { e[pre[cur]][2]-=minf; e[pre[cur]^1][2]+=minf; cur=prv[cur]; } sumflow+=minf; sum+=minf*d[2*n+2]; return 1; } int mincost(int &sumflow) { int sum=0; while(spfa(sum,sumflow)); return sum; } void init() { nume=0; memset(head,-1,sizeof(head)); } int main() { while(~scanf("%d%d",&n,&m)) { init(); int a,b,c; for(int i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&c); adde(a,b+n,1,c); } for(int i=1;i<=n;i++) { adde(0,i,1,0); adde(i+n,2*n+1,1,0); } adde(2*n+1,2*n+2,n,0); int sumflow=0; int ans=mincost(sumflow); if(sumflow!=n) printf("-1\n"); else { printf("%d\n",ans); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。