Orz胡伯涛《最小割模型在信息学竞赛中的应用》
建图方法:
设立源点S和汇点T,S和用户(共M个)连边,载流量为满足其要求的获利
T和中转站(共N个)连边,载流量为建立该中转站的费用
每个用户向对应的2个中转站连边,载流量为inf
对该图跑一遍最大流,求出最小割f,(∑Ci)-f就是答案
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> ; ; const int inf=0x3f3f3f3f; struct Edge { int to,next; int capacity; void assign(int t,int n,int c) { to=t; next=n; capacity=c; } }; Edge elist[*maxE]; int head[maxV]; int ecnt; void initEdge() { memset(head,-,sizeof(head)); ecnt=; } inline void addEdge(int from,int to,int capacity) { elist[ecnt].assign(to,head[from],capacity); head[from]=ecnt++; elist[ecnt].assign(); head[to]=ecnt++; } int N,M; int tot; int sink; //1~M:user M+1~N:station void input() { scanf("%d%d",&N,&M); initEdge(); sink=N+M+; int cost; ;i<=N;i++) { scanf("%d",&cost); addEdge(M+i,sink,cost); } tot=; int v1,v2; ;i<=M;i++) { scanf("%d%d%d",&v1,&v2,&cost); tot+=cost; addEdge(i,M+v1,inf); addEdge(i,M+v2,inf); addEdge(,i,cost); } } int layer[maxV]; std::queue<int> que; bool bfs() { memset(layer,,sizeof(layer)); layer[]=; que.push(); while(!que.empty()) { int cur=que.front(); que.pop(); ;e=elist[e].next) { int& to=elist[e].to; int& cp=elist[e].capacity; if(!layer[to] && cp) { layer[to]=layer[cur]+; que.push(to); } } } return layer[sink]; } int dfs(int cur,int flow) { if(cur==sink) return flow; ); ;e=elist[e].next) { int& to=elist[e].to; int& cp=elist[e].capacity; && cp) { int tp=dfs(to,std::min(flow,cp)); res+=tp; flow-=tp; elist[e].capacity-=tp; elist[e^].capacity+=tp; if(!flow) return res; } } return res; } int dinic() { ); ,inf); return res; } int main() { input(); printf("%d\n",tot-dinic()); ; }