From The Stupid
Bad at Coding
bzoj 1497 【NOI2006】最大获利 题解
starli
posted @ 2016年1月23日 14:31
in 网络流
, 497 阅读
原来不会做 看了论文才会写的 是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;
}
评论 (0)