【POJ】【2987】Firing

网络流/最大权闭合子图

　　胡伯涛论文里有讲……
　　sigh……细节处理太伤心了，先是count和ans输出弄反了，改过来顺序时又忘了必须先算出来ans！要是不执行一下Dinic的话count就无意义了……然后就是long long的问题……傻逼题白白WA了6次……sigh果然不能晚上搞……
  1 Source Code
  2 Problem: 2987        User: sdfzyhy
  3 Memory: 2664K        Time: 344MS
  4 Language: G++        Result: Accepted
  5 
  6     Source Code
  7 
  8     //POJ 2987
  9     #include<vector>
 10     #include<cstdio>
 11     #include<cstring>
 12     #include<cstdlib>
 13     #include<iostream>
 14     #include<algorithm>
 15     #define rep(i,n) for(int i=0;i<n;++i)
 16     #define F(i,j,n) for(int i=j;i<=n;++i)
 17     #define D(i,j,n) for(int i=j;i>=n;--i)
 18     #define pb push_back
 19     using namespace std;
 20     inline int getint(){
 21         int v=0,sign=1; char ch=getchar();
 22         while(ch<'0'||ch>'9'){ if (ch=='-') sign=-1; ch=getchar();}
 23         while(ch>='0'&&ch<='9'){ v=v*10+ch-'0'; ch=getchar();}
 24         return v*sign;
 25     }
 26     const int N=5100,M=300000,INF=~0u>>2;
 27     typedef long long LL;
 28     /******************tamplate*********************/
 29     int n,m;
 30     LL ans;
 31     struct edge{
 32         int from,to;
 33         LL v;
 34     };
 35     struct Net{
 36         edge E[M];
 37         int head[N],next[M],cnt;
 38         void add(int x,int y,LL v){
 39             E[++cnt]=(edge){x,y,v};
 40             next[cnt]=head[x]; head[x]=cnt;
 41             E[++cnt]=(edge){y,x,0};
 42             next[cnt]=head[y]; head[y]=cnt;
 43         }
 44         int s,t,cur[N],d[N],Q[N];
 45         void init(){
 46             n=getint();m=getint();
 47             ans=0;cnt=1;
 48             s=0;t=n+1;
 49             LL x,y;
 50             F(i,1,n){
 51                 x=getint();
 52                 if (x>=0) {add(s,i,x);ans+=x;}
 53                 else add(i,t,-x);
 54             }
 55             F(i,1,m){
 56                 x=getint(); y=getint();
 57                 add(x,y,INF);
 58             }
 59         }
 60         bool mklevel(){
 61             memset(d,-1,sizeof d);
 62             d[s]=0;
 63             int l=0,r=-1;
 64             Q[++r]=s;
 65             while(l<=r){
 66                 int x=Q[l++];
 67                 for(int i=head[x];i;i=next[i])
 68                     if (d[E[i].to]==-1 && E[i].v){
 69                         d[E[i].to]=d[x]+1;
 70                         Q[++r]=E[i].to;
 71                     }
 72             }
 73             return d[t]!=-1;
 74         }
 75         LL dfs(int x,LL a){
 76             if (x==t||a==0) return a;
 77             LL flow=0;
 78             for(int &i=cur[x];i && flow<a;i=next[i])
 79                 if (d[E[i].to]==d[x]+1 && E[i].v){
 80                     LL f=dfs(E[i].to,min(a-flow,E[i].v));
 81                     E[i].v-=f;
 82                     E[i^1].v+=f;
 83                     flow+=f;
 84                 }
 85             if (!flow) d[x]=-1;
 86             return flow;
 87         }
 88         LL Dinic(){
 89             LL flow=0;
 90             while(mklevel()){
 91                 F(i,s,t) cur[i]=head[i];
 92                 flow+=dfs(s,INF);
 93             }
 94             return flow;
 95         }
 96         bool vis[N];
 97         void dfs(int x){
 98             vis[x]=1;
 99             for(int i=head[x];i;i=next[i])
100                 if (!vis[E[i].to] && E[i].v) dfs(E[i].to);
101         }
102         void solve(){
103             ans=ans-Dinic();
104             int count=0;
105             memset(vis,0,sizeof vis);
106             dfs(s);
107             F(i,1,n) if (vis[i]) count++;
108             printf("%d %lld
",count,ans);
109         }
110     }G1;
111     int main(){
112     #ifndef ONLINE_JUDGE
113         freopen("2987.in","r",stdin);
114         freopen("2987.out","w",stdout);
115     #endif
116         G1.init();
117         G1.solve();
118         return 0;
119     }
View Code