题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=2039
题意：n 个人，雇佣每个人有一个费用，同时雇佣 (i,j) 收益为 2*E[i][j]，只雇佣其中一个费用为 E[i][j]，求最大总收益...
建模太神了... 怎么回事啊怎么回事啊还是学不会啊学不会啊怎么办啊怎么办啊...
- 每个人向汇点连一条权值为个人费用的边
- 对于两人中只雇佣一个人的费用 E[i][j]，从源点向每个人连过去...
- 对于同时雇佣两人的收益 2*E[i][j]，在 i,j 两人间连一条双向边
这么搞后一组割对应一组雇佣方案了，为什么呢，我们稍微想一想... 对于两个人 (i,j)，他们的状态只有都雇佣，雇一个，都不雇三种，对于第一种，它的割是割断 (1)，费用即为 cost[i]+cost[j]，对于第二种，割断 (3) 后割断一对 (1),(2)，第三种割断 (2)... 恰好覆盖了所以可能的割...
然而数据范围比较大，直接搞会 T，我们发现 (2) 连的边重边很多，我们处理一下，直接连总费用即可.... 代码如下：
对了.. 开 long long
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
#include <queue> #include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define N 1010 #define M 800010 #define inf 21000000000000ll #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll n,S,T; struct zgz { ll next,to,val; }edge[M]; ll cnt=2,head[M]; void add(ll from,ll to,ll val) { edge[cnt].to=to; edge[cnt].val=val; edge[cnt].next=head[from]; head[from]=cnt++; } ll tmp,sum[N],ans; queue<ll> q; ll d[N]; bool bfs() { memset(d,0,sizeof(d)); d[S]=1,q.push(S); while(!q.empty()) { ll x=q.front();q.pop(); for(ll i=head[x];i;i=edge[i].next) { ll to=edge[i].to,val=edge[i].val; if(!d[to]&&val) { d[to]=d[x]+1; q.push(to); } } } if(d[T])return 1; return 0; } ll dfs(ll x,ll v) { if(x==T||v==0)return v; ll ret=0; for(ll i=head[x];i;i=edge[i].next) { ll to=edge[i].to,val=edge[i].val; if(d[to]==d[x]+1) { ll f=dfs(to,min(v,val)); edge[i].val-=f,edge[i^1].val+=f; v-=f,ret+=f; if(v==0)break; } } if(ret==0)d[x]=-1; return ret; } int main() { n=read();S=0,T=n+1; for(int i=1;i<=n;i++) { tmp=read(); add(i,T,tmp);add(T,i,0); } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { tmp=read();ans+=tmp; if(i>=j)continue; sum[i]+=tmp,sum[j]+=tmp; add(i,j,tmp<<1);add(j,i,tmp<<1); } for(int i=1;i<=n;i++) { add(S,i,sum[i]); add(i,S,0); } while(bfs())ans-=dfs(S,inf); printf("%d",ans); } |
Comments | NOTHING