bzoj 1497 【NOI2006】最大获利 题解

starli posted @ 2016年1月23日 14:31 in 网络流 , 145 阅读
 
原来不会做 看了论文才会写的 是2007年胡伯涛的集训队论文 国家集训队2007论文集7.胡伯涛《最小割模型》.pdf
显然 我们发现这是一个图论模型 考虑网络流
要最大化的是 取的用户值-建的中转站的值
变形一下 所有用户值-不取的用户-建的中转站的值
要最小化的就是 不取的用户+建的中转站的值
构图 新建源汇s,t 将s连向所有的用户 容量为获利 所有的中转站连向t 容量为费用 用户指向两个需求 容量为﹢∞
我们只要求一个最小割,再用所有的用户值减去这个割的大小即可
去掉的边中 s与用户相连的边 表示这个用户不选
           t与中转站相连的边 表示这个中转站要建
下证明 最小割对应一个取的方案 可以使所有用户都满足
假设存在一条通路 设这条通路 上用户为a 中转站为b 那么 由上述定义 我们要选择 a用户 又不建这个中转站 显然这是不正确的 又这个割是最小的 那么一定符合题目要求 <-这句话就是瞎扯淡的
我证明的有问题 详情还是要看一下论文的
 
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=200000;
int e[N*2],pre[N*2],c[N*2],flow[N*2],now[N],d[N],vis[N],tail=1,cur[N],n,m,q[N],v,ans,a,b;
void add(int u,int v,int cap){e[++tail]=v;c[tail]=cap;pre[tail]=now[u];now[u]=cur[u]=tail;}
bool bfs(int s,int t){
	int l=0,r=0;
	memset(vis,0,sizeof(vis));
	q[++r]=s;d[s]=0;vis[s]=1;
	while(l<r){
		int x=q[++l];
		for(int i=now[x];i;i=pre[i]) if(!vis[e[i]] && c[i]>0) {
			q[++r]=e[i];vis[e[i]]=1;d[e[i]]=d[x]+1;
		}
	}
	return vis[t];
}
int dfs(int x,int a){
	if(x==n+m+2 || a==0) return a;
	int flow=0,f;
	for(int &i=cur[x];i;i=pre[i]) 
		if(d[x]+1==d[e[i]] && (f=dfs(e[i],min(a,c[i])))>0){
			c[i]-=f;c[i^1]+=f;flow+=f;a-=f;
			if(a==0) break;
		}
	return flow;
}
void print(int a){
	printf("Edges of %d :",a);
	for(int i=now[a];i;i=pre[i]) if(c[i]) printf("%d(%d) ",e[i],c[i]);printf("\n");
}
int main(){
	freopen("1497.in","r",stdin);freopen("1497.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&v),add(i,n+m+2,v),add(n+m+2,i,0);
	for(int i=1;i<=m;i++) {
		scanf("%d%d%d",&a,&b,&v);
		add(n+m+1,i+n,v);
		add(i+n,n+m+1,0);
		add(i+n,a,2099999999+1);add(a,i+n,0);
		add(i+n,b,2099999999+1);add(b,i+n,0);
		ans+=v;
	}
	//print(11);for(int i=6;i<=10;i++) print(i);for(int i=1;i<=5;i++) print(i);print(12);
	while(bfs(n+m+1,n+m+2)) {
		for(int i=1;i<=n+m+2;i++) cur[i]=now[i];
		ans-=dfs(n+m+1,2099999999);
	}
	printf("%d",ans);
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter