bzoj5403:marshland费用流

Description

Input

Output

Sample Input

Input 1
3 3 1
0 1 0
2 0 1
0 1 0
1 3
Input 2
3 3 4
0 2 0
0 0 4
0 3 0
1 3
2 1
2 2
3 1

Sample Output

Output 1
3
Output 2
9

Data Constraint

分析&＃xff1a;
今天模拟赛&＃xff0c;出题人做了自己出的题目……
出题人表示看到题目非常尴尬&＃xff0c;然后ak了。

设$x\&＃43;y$为奇数的为黑点&＃xff0c;否则为白点。
显然我们选一个黑点&＃xff0c;就要在上下两个中选一个白点和一个在左右两个中选一个白点。
那么就可以给费用流建模了。我们把横坐标为偶数的白点放在左边&＃xff0c;横坐标为奇数的放右边。黑点分成两个点&＃xff0c;这两个点连一条费用为v(x,y)v_{(x,y)}v(x,y)​的边&＃xff0c;横坐标为偶数的白点点连左边的黑点&＃xff0c;右边的黑点连横坐标为奇数的白点&＃xff0c;然后连上源汇就好了。显然一次只会加$1$点流量&＃xff0c;所以当跑了$m$次&＃xff0c;或最长路为负即可退出&＃xff08;显然不一定要加上所有的点&＃xff09;。
考场上一直在想怎样一次流掉这两个点&＃xff0c;一直把这个放在一边&＃xff0c;然后就想不出来了。

代码&＃xff1a;

/**************************************************************Problem: 5403User: liangzihaoLanguage: C&＃43;&＃43;Result: AcceptedTime:1264 msMemory:3872 kb
****************************************************************/#include
#include
#include
#include const int maxn&＃61;1e4&＃43;7;
const int maxe&＃61;1e5&＃43;7;
const int inf&＃61;0x3f3f3f3f;using namespace std;int n,m,k,x,ans,cnt,s,t,y;
int ls[maxn],dis[maxn],vis[maxn],pre[maxn],a[100][100],b[maxn];queue q;struct edge{int x,y,w,c,op,next;
}g[maxe];void add(int x,int y,int w,int c)
{g[&＃43;&＃43;cnt]&＃61;(edge){x,y,w,c,cnt&＃43;1,ls[x]};ls[x]&＃61;cnt;g[&＃43;&＃43;cnt]&＃61;(edge){y,x,0,-c,cnt-1,ls[y]};ls[y]&＃61;cnt;
}int po(int x,int y)
{return (x-1)*n&＃43;y;
}bool spfa()
{ while (!q.empty()) q.pop();for (int i&＃61;s;i<&＃61;t;i&＃43;&＃43;){dis[i]&＃61;-inf;vis[i]&＃61;0;}dis[s]&＃61;0;q.push(s);vis[s]&＃61;1;while (!q.empty()){int x&＃61;q.front();q.pop();for (int i&＃61;ls[x];i>0;i&＃61;g[i].next){int y&＃61;g[i].y;if ((g[i].w) && (dis[y]0) return 1;return 0;
}void mcf()
{int i&＃61;t,x&＃61;1e9;while (i!&＃61;s){x&＃61;min(x,g[pre[i]].w);i&＃61;g[pre[i]].x;}i&＃61;t;while (i!&＃61;s){g[pre[i]].w-&＃61;x;g[g[pre[i]].op].w&＃43;&＃61;x;ans-&＃61;g[pre[i]].c*x;i&＃61;g[pre[i]].x;}
}
int main()
{scanf("%d%d%d",&n,&m,&k);s&＃61;0; t&＃61;n*n*2&＃43;1;for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for (int j&＃61;1;j<&＃61;n;j&＃43;&＃43;){scanf("%d",&a[i][j]);}}for (int i&＃61;1;i<&＃61;k;i&＃43;&＃43;){scanf("%d%d",&x,&y);b[po(x,y)]&＃61;1;} for (int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){for (int j&＃61;1;j<&＃61;n;j&＃43;&＃43;){ans&＃43;&＃61;a[i][j];if (b[po(i,j)]) continue;if ((i&＃43;j)%2&＃61;&＃61;0){if (i%2&＃61;&＃61;0){add(s,po(i,j),1,0);if (i>1) add(po(i,j),po(i-1,j),1,0);if (j>1) add(po(i,j),po(i,j-1),1,0);if (i1) add(n*n&＃43;po(i-1,j),po(i,j),1,0);if (j>1) add(n*n&＃43;po(i,j-1),po(i,j),1,0);if (i}
&＃xfeff;