题意：
给一张二分图，每个点与两个特定点又一条边相连，边权非负，让你给这个二分图每个点一个顶标，让每一条边两端顶标和大于等于这条边。求出最小顶标和。
这当然是翻译过的题目。。。
原题：
小Y和小P无聊的时候就喜欢玩游戏，但是每次小P都输给了小Y。终于有一天，你看不过去了，决定帮小P一把。
游戏是这样的，一个N*M的棋盘（保证n或m中，至少有一个为偶数）。相邻格子之间有一个给定的正整数权值。要你给这些格子填上一些值，使得相邻两个格子本身的权值之和，要大于等于他们之间给定的权值。并且要使得所有格子权值之和最小。
不过也挺显然的。。。当然在你学完KM后对这种思想还是非常敏感。。如果没学过会怎么乱搞呢？。。。因确斯汀。
SOL：
还有题解？。。。这不就跑个KM顶标什么的都出来了。。。数据较大用个领接表。。也就复习一下KM
CODE：
/*==========================================================================
# Last modified: 2016-03-04 09:11
# Filename: t2.cpp
# Description:
==========================================================================*/
#define me AcrossTheSky
#include <cstdio>
#include <cmath>
#include <ctime>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> #include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector> #define lowbit(x) (x)&(-x)
#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)
#define FORP(i,a,b) for(int i=(a);i<=(b);i++)
#define FORM(i,a,b) for(int i=(a);i>=(b);i--)
#define ls(a,b) (((a)+(b)) << 1)
#define rs(a,b) (((a)+(b)) >> 1)
#define getlc(a) ch[(a)][0]
#define getrc(a) ch[(a)][1] #define maxn 11050
#define maxm 50000
#define pi 3.1415926535898
#define _e 2.718281828459
#define INF 1070000000
using namespace std;
typedef long long ll;
typedef unsigned long long ull; template<class T> inline
void read(T& num) {
bool start=false,neg=false;
char c;
num=0;
while((c=getchar())!=EOF) {
if(c=='-') start=neg=true;
else if(c>='0' && c<='9') {
start=true;
num=num*10+c-'0';
} else if(start) break;
}
if(neg) num=-num;
}
/*==================split line==================*/
struct Edge{
int to,len;
}e[maxm];
int s[maxn],t[maxn],slack[maxn],lx[maxn],ly[maxn];
bool color[maxn],S[maxn],T[maxn],vis[maxn];
int out[5050][5050],link[maxn],ord[maxn],first[maxn],next[maxm];
int sumt=0,sums=0,sume=0;
int n,m;
void addedge(int x,int y,int l){
sume++; e[sume].to=y; e[sume].len=l;
next[sume]=first[x]; first[x]=sume;
}
void updata(){
int a=INF;
FORP(j,1,sumt) if (!T[j]) a=min(a,slack[j]);
FORP(i,1,sums) if (S[i]) lx[i]-=a;
FORP(i,1,sumt) if (T[i]) ly[i]+=a;
else slack[i]-=a;
return;
}
bool match(int x){
S[x]=true;
//FORP(i,1,sumt){
for (int p=first[s[x]]; p!=-1; p=next[p]){
int i=ord[e[p].to];
if (T[i]) continue;
if (lx[x]+ly[i]==e[p].len){//way[s[x]][t[i]]){
T[i]=true;
if (!link[i] || match(link[i])){
link[i]=x;
return true;
}
}
else slack[i]=min(slack[i],lx[x]+ly[i]-e[p].len);//way[s[x]][t[i]]);
}
return false;
}
void KM(){
memset(lx,0,sizeof(lx));
memset(ly,0,sizeof(ly));
memset(link,0,sizeof(link));
FORP(i,1,sums)
for (int j=first[s[i]];j!=-1;j=next[j])
lx[i]=max(lx[i],e[j].len);
//FORP(j,1,sumt) lx[i]=max(lx[i],way[s[i]][t[j]]); FORP(i,1,sums){
FORP(j,1,sumt) slack[j]=INF;
while (1){
memset(S,false,sizeof(S));
memset(T,false,sizeof(T));
if (match(i)) break;
else updata();
}
}
}
void get(int node,int v){
int x=node/m+1,y=node%m;
if (y==0) y=m,x--;
out[x][y]=v;
}
void paint(int x,int y,bool fa){
int node=(x-1)*m+y;
if (vis[node]) return;
vis[node]=true;
color[node]=!fa;
if (color[node]) s[++sums]=node,ord[node]=sums;
else t[++sumt]=node,ord[node]=sumt;
if (y==0) y=m,x--;
if (x<n) paint(x+1,y,color[node]);
if (y<m) paint(x,y+1,color[node]);
}
int main(){
read(n); read(m);
memset(first,-1,sizeof(first));
FORP(i,1,n){
FORP(j,1,2*m) {
int x; read(x);
if (j>2*(m-1)+1 || (i==n && j%2==1)) continue;
if (j%2==1) {
int node1=(i-1)*m+j/2+1;
int node2=node1+m;
addedge(node1,node2,x);
addedge(node2,node1,x);
}
else {
int node1=(i-1)*m+j/2;
int node2=node1+1;
addedge(node2,node1,x);
addedge(node1,node2,x);
}
}
}
memset(vis,false,sizeof(vis));
paint(1,1,false); KM();
int ans=0;
FORP(i,1,sums) {ans+=lx[i]; get(s[i],lx[i]);}
FORP(i,1,sumt) {ans+=ly[i]; get(t[i],ly[i]);}
printf("%d\n",ans);
FORP(i,1,n){
FORP(j,1,m) printf("%d ",out[i][j]);
cout << endl;
}
}