poj2987 求最大权闭合回路

• 建图差不多和以前做的差不多，就是最后询问这个闭合子图有多少个的时候，只要输出这个图的S集合，就是进行dfs能遍历到的点一定在S集合中，不能遍历到的点在T集合中

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn=5555;
const long long INF=1LL<<60;
typedef long long LL;
struct Dinic
{struct Edge{LL from,to,cap,flow;Edge(LL cfrom=0,LL cto=0,LL ccap=0,LL cflow=0){from=cfrom;  to=cto; cap=ccap; flow=cflow;}};int n,m,s,t;vectoredges;vector<int>G[maxn];bool vis[maxn];int d[maxn];int cur[maxn];void init(int n){m=0;this->n=n;for(int i=0; i<=n; i++)G[i].clear();edges.clear();}void addEdge(LL from,LL to, LL cap){edges.push_back(Edge(from,to,cap,0) );edges.push_back(Edge(to,from,0,0));m+=2;G[from].push_back(m-2);G[to].push_back(m-1);}bool BFS(){memset(vis,0,sizeof(vis));queue<int>Q;Q.push(s);d[s]=0;vis[s]=1;while(!Q.empty()){int x=Q.front(); Q.pop();for(int i=0; iif(vis[e.to]==false&&e.cap>e.flow){vis[e.to]=1;d[e.to]=d[x]+1;Q.push(e.to);}}}return vis[t];}LL DFS(int x,LL a){if(x==t||a==0)return a;LL flow=0,f;for(int &i=cur[x]; iif(d[x]+1==d[e.to]&&(f=DFS(e.to,dd))>0){e.flow+=f;edges[G[x][i]^1].flow-=f;flow+=f;a-=f;if(a==0)break;}}return flow;}LL Maxflow(int s,int t){this->s=s;this->t=t;LL flow=0;while(BFS()){memset(cur,0,sizeof(cur));flow+=DFS(s,INF);}return flow;}void find(int cur){vis[cur]=true;for(int i=0; iif(vis[e.to]||e.cap<=e.flow)continue;find(e.to);}}int solve(){memset(vis,0,sizeof(vis));for(int i=0; iif(vis[e.to]||e.cap<=e.flow)continue;find(e.to);}int ans=0;for(int i=1; i<=n-2; i++)ans+=vis[i];return ans;}
}T;
int P[maxn];
int main()
{int n,m;while(scanf("%d%d",&n,&m)==2){LL S1=0,S2=0;T.init(n+2);for(int i=1; i<=n; i++){scanf("%d",&P[i]);if(P[i]>0){S1+=P[i];S2+=P[i];T.addEdge(n+1,i,P[i]);}else{S1+=-P[i];T.addEdge(i,n+2,-P[i]);}}for(int i=1; i<=m; i++){int a,b;scanf("%d%d",&a,&b);T.addEdge(a,b,S1);}LL a1=T.Maxflow(n+1,n+2);LL a2=T.solve();printf("%I64d %I64d\n",a2,S2-a1);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！