[bzoj2127]happiness
摘要:
這題學長說可以轉化為最大權閉合子圖,然鵝我當時沒有聽懂。看了題解,大家有的在列方程搞事情,我也不是很懂。有一篇部落格給了一張圖,我拿著圖搞了搞,好像會了一種演算法。(不算是自己想出來的吧,圖已經給了大致思路,只能說細節是自己實現的)。
先來盜一下圖。
這個圖...
- 這題學長說可以轉化為最大權閉合子圖,然鵝我當時沒有聽懂。看了題解,大家有的在列方程搞事情,我也不是很懂。有一篇部落格給了一張圖,我拿著圖搞了搞,好像會了一種演算法。(不算是自己想出來的吧,圖已經給了大致思路,只能說細節是自己實現的)。
- 先來盜一下圖。
- 這個圖好nb,看懂這張圖這題基本就做完了。我們要給每個人選一個科目,讓總的價值最大。這類問題如何用網路流解呢?還是從簡入手,我們先考慮只有兩個人的情況,這就是這張圖的由來。
- 兩個人有四種情況,( \(x\) 選文, \(y\) 選理)、( \(x\) 選理, \(y\) 選文)、(兩人都選文)、(兩人都選理)。題目讓求最大值,而我們網路流求最大流最小割,求的都是最小值。因此,我們需要轉化一下。先把所有情況對答案的貢獻累加,然後跑最小割去掉最小代價使方案合法。
- 我們先把 \(x\) 選文、 \(x\) 選理、 \(y\) 選文、 \(y\) 選理、 \(x\) 和 \(y\) 都選文、 \(x\) 和 \(y\) 都選理的代價累加。這時,按照圖中那樣建圖,割掉一條邊代表不使用這個狀態。從 \(S\) 到 \(x\) 連一條邊,代表 \(x\) 選了文,其他同理。向 \(T\) 連邊代表選了理。你發現,這樣建圖的好處在於,你割的方案正好對應了四種情況。
- 這時候,就是合理給邊賦值,跑最小割了。使 \(S\) 到 \(x\) 的邊容量為 \(x\) 選文的價值加上同時選文價值的一半。 \(y\) 同理。使 \(x\) 到 \(T\) 的邊容量為 \(x\) 選理的價值加上同選理的價值的一半, \(y\) 同理。 \(x\) 向 \(y\) 連邊的容量為同選文價值的一半加上同選理價值的一半。這樣,假如你割掉了 \(a\) , \(d\) ,那麼你必須割掉 \(e\) 。代表你選擇去掉 \(x\) 選文的情況、 \(y\) 選理的情況,答案就是初始 \(sum-maxflow\) 。
- 拓展到多點也是一樣,注意這題卡精度,可以先把權值乘2最後再除掉。
#include<bits/stdc++.h> #define ll long long using namespace std; const int N=2e4+10; const int M=2e5+10; const int inf=1e9; map<pair<int,int>,int>w; int n,m,s,t,tot=1,we[N],li[N],ver[M],Next[M],lin[N],edge[M],d[N],maxflow,flow,sum; int cal(int i,int j){return (i-1)*m+j;} void add(int x,int y,int z){ ver[++tot]=y;Next[tot]=lin[x];lin[x]=tot;edge[tot]=z; ver[++tot]=x;Next[tot]=lin[y];lin[y]=tot;edge[tot]=0; } bool bfs(){ memset(d,0,sizeof(d)); queue<int>q; d[s]=1,q.push(s); while(q.size()){ int x=q.front();q.pop(); for(int i=lin[x];i;i=Next[i]){ int y=ver[i]; if(!d[y]&&edge[i]){ d[y]=d[x]+1; q.push(y); if(y==t) return 1; } } } return 0; } int dinic(int x,int flow){ if(x==t) return flow; int rest=flow; for(int i=lin[x];i&&rest;i=Next[i]){ int y=ver[i]; if(d[y]==d[x]+1&&edge[i]){ int k=dinic(y,min(edge[i],rest)); if(!k) d[y]=0; rest-=k;edge[i]-=k;edge[i^1]+=k; if(!rest) return flow-rest; } } return flow-rest; } int main(){ //freopen("1.in","r",stdin); //freopen("1.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",&we[cal(i,j)]),sum+=we[cal(i,j)],we[cal(i,j)]*=2; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) scanf("%d",&li[cal(i,j)]),sum+=li[cal(i,j)],li[cal(i,j)]*=2; for(int i=2;i<=n;++i) for(int j=1;j<=m;++j){ int c;scanf("%d",&c);sum+=c; c*=2; we[cal(i,j)]+=c/2;we[cal(i-1,j)]+=c/2; w[make_pair(cal(i,j),cal(i-1,j))]=c/2; } for(int i=2;i<=n;++i) for(int j=1;j<=m;++j){ int c;scanf("%d",&c);sum+=c; c*=2; li[cal(i,j)]+=c/2;li[cal(i-1,j)]+=c/2; c/=2; c+=w[make_pair(cal(i,j),cal(i-1,j))]; add(cal(i,j),cal(i-1,j),c);add(cal(i-1,j),cal(i,j),c); } for(int i=1;i<=n;++i) for(int j=2;j<=m;++j){ int c;scanf("%d",&c);sum+=c; c*=2; we[cal(i,j)]+=c/2;we[cal(i,j-1)]+=c/2; w[make_pair(cal(i,j),cal(i,j-1))]=c/2; } for(int i=1;i<=n;++i) for(int j=2;j<=m;++j){ int c;scanf("%d",&c);sum+=c; c*=2; li[cal(i,j)]+=c/2;li[cal(i,j-1)]+=c/2; c/=2; c+=w[make_pair(cal(i,j),cal(i,j-1))]; add(cal(i,j),cal(i,j-1),c);add(cal(i,j-1),cal(i,j),c); } s=0,t=n*m+1; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j){ add(s,cal(i,j),we[cal(i,j)]); add(cal(i,j),t,li[cal(i,j)]); } while(bfs()){ while(flow=dinic(s,inf)) maxflow+=flow; } printf("%d\n",sum-maxflow/2); return 0; }