首先黑白染色,源点到黑点连条边,值为格子数值,然后白色点到汇点也连条这样的边,然后每个黑点对与其相连的白点连条无穷大的边,然后求个最小割,答案就是所有格子数值和减去这个最小割。
#include<cstdio>
#include<cstring>
int n,m,cnt,s,t;
int mp[51][51],head[3000],dis[3000],gap[3000];
const int inf=1<<30;
struct EDGE
{
int to,f,nxt;
}edge[15000];
int min(int a,int b)
{
return a<b?a:b;
}
void init()
{
cnt=0;
memset(head,-1,sizeof(head));
memset(gap,0,sizeof(g......
阅读全文