【题目大意】
参见NOIP的传纸条。
【算法分析】
直接费用流~
对于时间复杂度分析一下：由于只增广两次，所以复杂度是O(2*SPFA)。
不需要担心点太多了~
【CODE】
#include
const int E=2160111;
const int INF=1000000000;
struct gtp{int x,y,next,op,w,c;}g[E];
int n,e,S,T,cost;
int pos[622][622],ls[N],d[N],v[N],list[N],fa[N];
inline void addedge(int x,int y,int c,int w){
e++;
g[e].x=x; g[e].y=y; g[e].c=c; g[e].w=w;
g[e].next=ls[x]; ls[x]=e; g[e].op=e+1;
e++;
g[e].x=y; g[e].y=x; g[e].c=0; g[e].w=-w;
g[e].next=ls[y]; ls[y]=e; g[e].op=e-1;
}
void init(){
int i,j,tmp=0,w;
e=0;
for (i=1;i<=2*n*n+2;i++) ls[i]=0;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
pos[i][j]=++tmp;
for (i=1;i<=n;i++)
for (j=1;j<=n;j++){
scanf("%d",&w);
addedge(pos[i][j],pos[i][j]+n*n,1,w);
if (i
S=n*n*2+1; T=S+1;
addedge(S,1,2,0);
addedge(n*n*2,T,2,0);
addedge(1,n*n+1,1,0);
addedge(n*n,n*n*2,1,0);
}
void spfa(){
for (int i=1;i<=T;i++){
d[i]=-INF;
v[i]=0;
}
int head=0,tail=1,t;
list[1]=S; v[S]=1; d[S]=0;
while (head!=tail){
head++; if (head>=N) head=0;
for (t=ls[list[head]];t;t=g[t].next)
if (g[t].c && d[g[t].x]+g[t].w>d[g[t].y]){
d[g[t].y]=d[g[t].x]+g[t].w;
fa[g[t].y]=t;
if (!v[g[t].y]){
v[g[t].y]=1;
tail++; if (tail>=N) tail=0;
list[tail]=g[t].y;
}
}
v[list[head]]=0;
}
}
void change(){
cost+=d[T];
for (int i=T;i!=S;i=g[fa[i]].x){
g[fa[i]].c–;
g[g[fa[i]].op].c++;
}
}
void work(){
cost=0;
spfa();
change();
spfa();
change();
}
int main(){
while (scanf("%d",&n)!=EOF){
init();
work();
printf("%dn",cost);
}
}
(借一下野牛的图。。。)