[POJ 2987]最大权闭合图

【题目大意】给出每个点的权值和依赖关系，求两个东西:1、求取得最大权值时所取的最小点数。2、取得的最大权值。

【算法分析】直接最大权闭合图然后dfs求割就可以了。
不过我这个我不知道怎么证明正确，但是确实AC了。要保证正确的话，我觉得还是要放大边权。
即先B[i]=B[i]*n-1（正的B[i]）B[i]=B[i]*n+1（负的B[i]），然后最后除回来取整就是答案，然后如果用少一个人，-1的数量就少了，这样就能保证是最小点数。
不过听说我这个也是正确的，只是我不会证明罢了。。。

【其它】1A
6393387 edward2 2987 Accepted 2592K 735MS G++ 2260B 2010-01-31 19:34:57
【CODE】
#include #include #include #define N 6000
#define E 500000
#define inf 0x7FFFFFFF
struct gtp{int x,y,next,c,op;}g[E];
int n,m,e;
int ls[N],fa[N],cur[N],num[N],d[N],b[N],v[N];
long long flow;

inline void addedge(int x,int y,int c){
e++;
g[e].x=x; g[e].y=y; g[e].c=c; g[e].op=e+1; g[e].next=ls[x]; ls[x]=e;
e++;
g[e].x=y; g[e].y=x; g[e].c=0; g[e].op=e-1; g[e].next=ls[y]; ls[y]=e;
}

void init(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
scanf("%d",&b[i]);
if (b[i]>0) addedge(0,i,b[i]);
else addedge(i,n+1,-b[i]);
}
for (int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
addedge(x,y,inf);
}
}

void relabel(int k){
int mm=n+2;
cur[k]=ls[k];
for (int t=ls[k];t!=0;t=g[t].next)
if (g[t].c && d[g[t].y] d[k]=mm+1;
}

void change(){
int nf=inf;
for (int i=n+1;i!=0;i=g[fa[i]].x)
if (g[fa[i]].c for (int i=n+1;i!=0;i=g[fa[i]].x){
g[fa[i]].c-=nf;
g[g[fa[i]].op].c+=nf;
}
flow+=nf;
}

void sap(){
memset(d,0,sizeof(d));
memset(num,0,sizeof(num));
for (int i=0;i<=n+1;i++) cur[i]=ls[i];
num[0]=n+2; flow=0;
int i=0;
while (d[0] for (;cur[i];cur[i]=g[cur[i]].next)
if (g[cur[i]].c && d[g[cur[i]].y]+1==d[i]) break;
if (!cur[i]){
if (!–num[d[i]]) break;
relabel(i);
num[d[i]]++;
if (i!=0) i=g[fa[i]].x;
}
else{
fa[g[cur[i]].y]=cur[i];
i=g[cur[i]].y;
if (i==n+1){
change();
i=0;
}
}
}
}

void dfs(int k){
v[k]=1;
for (int t=ls[k];t!=0;t=g[t].next)
if (g[t].c && !v[g[t].y]) dfs(g[t].y);
}

void print(){
memset(v,0,sizeof(v));
dfs(0);
int num=0; long long sum=0;
for (int i=1;i<=n;i++){
if (v[i]) num++;
if (b[i]>0) sum+=b[i];
}
printf("%d %lldn",num,sum-flow);
}

int main(){
init();
sap();
print();
}