首页 > 代码库 > hdu 3879 最大权闭合图(裸题)
hdu 3879 最大权闭合图(裸题)
/* 裸的最大权闭合图 解:参见胡波涛的《最小割模型在信息学竞赛中的应用》 */ #include<stdio.h> #include<string.h> #include<stdlib.h> #include<queue> using namespace std; #define N 55100//刚开始开的是5100一直越界应该是n+m #define NN 510000 #define inf 0x3fffffff struct node { int u,v,w,next; }bian[NN*8]; int head[N],yong,dis[N],work[N]; void init() { yong=0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int w) { bian[yong].v=v; bian[yong].w=w; bian[yong].next=head[u]; head[u]=yong++; } int bfs(int s,int t) { memset(dis,-1,sizeof(dis)); queue<int>q; q.push(s); dis[s]=0; while(!q.empty()) { int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=bian[i].next) { int v=bian[i].v; if(bian[i].w&&dis[v]==-1) { dis[v]=dis[u]+1; q.push(v); if(v==t) return 1; } } } return 0; } int dfs(int s,int limit,int t) { if(s==t)return limit; for(int &i=work[s];i!=-1;i=bian[i].next) { int v=bian[i].v; if(bian[i].w&&dis[v]==dis[s]+1) { int tt=dfs(v,min(limit,bian[i].w),t); if(tt) { bian[i].w-=tt; bian[i^1].w+=tt; return tt; } } } return 0; } int dinic(int s,int t) { int ans=0; while(bfs(s,t)) { memcpy(work,head,sizeof(head)); while(int tt=dfs(s,inf,t)) ans+=tt; } return ans; } int main(){ int n,m,i,k,sum,u,v,w,s,t; while(scanf("%d%d",&n,&m)!=EOF) { init(); s=0;t=n+m+1; for(i=1;i<=n;i++) { scanf("%d",&k); addedge(i,t,k); addedge(t,i,0); } sum=0; for(i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); addedge(s,i+n,w); addedge(i+n,s,0); addedge(i+n,u,inf); addedge(u,i+n,0); addedge(i+n,v,inf); addedge(v,i+n,0); sum+=w; } printf("%d\n",sum-dinic(s,t)); } return 0;}
hdu 3879 最大权闭合图(裸题)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。