|
|
Posted on 2010-09-30 19:50 成幸毅 阅读(563) 评论(0) 编辑 收藏 引用
建模很简单，设置源点连接正权点，边权为该点值，负权点连接汇点，边权点为该点的绝对值，输入的边权值设为INF，然后求最大流，然后让正权点值的累加和减去最大流就是闭合图的最大权。《最小割模型在信息学竞赛中的应用》有详细的证明。
 #include <iostream>
using namespace std;
const int N=20010;
int NN;
const int MAXE=200010;
const int INF=1<<30;
int head[N];
int u,v;
int value;
int e[N];
bool tnt[N];
struct Edge
   {
 int v,next,w;
 }edge[MAXE * 5];
int cnt,n,m,s,t;
void addedge(int u,int v,int w)
{
edge[cnt].v=v;
edge[cnt].w=w;
edge[cnt].next=head[u];
head[u]=cnt++;
edge[cnt].v=u;
edge[cnt].w=0;
edge[cnt].next=head[v];
head[v]=cnt++;
}
__int64 sap()
{
memset(e,0,sizeof(e));
int pre[N],cur[N],dis[N],gap[N];
__int64 flow=0,aug=INF,u;
bool flag;
for(int i=0;i<=NN;i++)
  {
gap[i]=dis[i]=0;
 }
gap[s]=NN;
u=pre[s]=s;
while(dis[s]<NN)
{
flag=0;
for(int j= head[u];j!=-1;j=edge[j].next)
{
int v=edge[j].v;
if(edge[j].w>0&&dis[u]==dis[v]+1)
{
flag=1;
if(edge[j].w<aug) aug=edge[j].w;
e[u] = j;
pre[v]=u;
u=v;
if(u==t)
{
flow+=aug;
while(u!=s)
{
u=pre[u];
edge[e[u]].w-=aug;
edge[e[u]^1].w+=aug;
}
aug=INF;
}
break;
}
}
if(flag)
continue;
int mindis=NN;
for(int j=head[u];j!=-1;j=edge[j].next)
{
int v=edge[j].v;
if(edge[j].w>0&&dis[v]<mindis)
{
mindis=dis[v];
e[u]=j;
}
}
if((--gap[dis[u]])==0)
break;
gap[dis[u]=mindis+1]++;
u=pre[u];
}
return flow;
}
void dfs(int u) {
if(u == t) return;
tnt[u] = true;
for(int addr = head[u]; addr != -1; addr = edge[addr].next) {
if(edge[addr].w > 0 && !tnt[edge[addr].v])
dfs(edge[addr].v);
}
}
int main() {
while(scanf("%d%d",&n,&m) != EOF) {
memset(head,-1,sizeof(head));
memset(tnt,0,sizeof(cnt));
s = 0,t = n+1;
NN = t+1;
__int64 sum = 0;
int tot = 0;
for(int i = 1; i <= n; i++) {
scanf("%d",&value);
if(value <= 0) {
addedge(i,t,-value);
}
else {
addedge(s,i,value);
sum += value;
}
}
for(int j = 1; j <= m; j++) {
scanf("%d%d",&u,&v);
addedge(u,v,INF);
}
__int64 ans = sap();
dfs(0);
for(int i = 1; i <= n; i++) {
if(tnt[i])
tot++;
}
printf("%d %I64d\n",tot,sum - ans);
}
// system("pause");
return 0;
}
|