CF 316C2(Tidying Up-二分图最大边权) (二)

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Rep(i,n) for(int i=0;i #define Fork(i,k,n) for(int i=k;i<=n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define RepD(i,n) for(int i=n;i>=0;i--)
#define MAXN (80*80+10)
#define MAXL (80+10)
#define MAXM (MAXL*MAXL*4+MAXN*4)
#define INF (2139062143)
int q[MAXN*8],d[MAXN],pr[MAXN],ed[MAXN],b[MAXN];
int edge[MAXM],next[MAXM],cost[MAXM],weight[MAXM],pre[MAXN],size=1;
void addedge(int u,int v,int w,int c)
{
edge[++size]=v;
weight[size]=w;
cost[size]=c;
next[size]=pre[u];
pre[u]=size;
}
void addedge2(int u,int v,int w,int c){addedge(u,v,w,c),addedge(v,u,0,-c);}
bool SPFA(int s,int t)
{
memset(d,127,sizeof(d));
memset(b,0,sizeof(b));
d[q[1]=s]=0;b[s]=1;
int head=1,tail=1;
while (head<=tail)
{
int now=q[head++];
Forp(now)
{
int &v=edge[p];
if (weight[p]&&d[now]+cost[p] {
d[v]=d[now]+cost[p];
if (!b[v]) b[v]=1,q[++tail]=v;
pr[v]=now,ed[v]=p;
}
}
b[now]=0;
}
return d[t] }
int CostFlow(int s,int t)
{
int totcost=0;
while (SPFA(s,t))
{
int flow=INF;
for(int x=t;x^s;x=pr[x]) flow=min(flow,weight[ed[x]]);
totcost+=flow*d[t];
for(int x=t;x^s;x=pr[x]) weight[ed[x]]-=flow,weight[ed[x]^1]+=flow;
}
return totcost;
}
int n,m,a[MAXL][MAXL];
int no(int i,int j){return (i-1)*m+j;}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
cin>>n>>m;
int s=n*m+1,t=n*m+2;
For(i,n) For(j,m) cin>>a[i][j];
For(i,n) For(j,m)
{
if (i+j&1) addedge2(s,no(i,j),1,0);
else addedge2(no(i,j),t,1,0);
if (j {
if (i+j&1) addedge2(no(i,j),no(i,j+1),1,a[i][j]!=a[i][j+1]);
else addedge2(no(i,j+1),no(i,j),1,a[i][j]!=a[i][j+1]);
}
if (i {
if (i+j&1) addedge2(no(i,j),no(i+1,j),1,a[i][j]!=a[i+1][j]);
else addedge2(no(i+1,j),no(i,j),1,a[i][j]!=a[i+1][j]);
}
}
cout< return 0;
}