题意:一个城市有n座行政楼和m座避难所，现发生核战，要求将避难所中的人员全部安置到避难所中，每个人转移的费用为两座楼之间的曼哈顿距离+1,题目给了一种方案，问是否为最优方案,即是否全部的人员转移费用之和最小?若不是，输出SUBOPTIMAL,之后输出转移矩阵Ei,j.即第i座行政楼中Ei,j个人转移到第j座避难所;输出的不必是最优转移方案，只要比题解的sum小即可；
思路:直接建一个残量网络，即按照开始建的原图跑完最小费用流之后剩下的网络，行政楼和避难所之间的原图连边正向容量为inf,反向为0。之后反向从汇点t跑最短路，看是否存在一个负圈，若存在负圈则说明题目解的并不是最优解，这时找到圈中一点，把圈中权值为正(正向边)的流量-1,为负的流量加1即可；
负圈:圈中所有边的流量为正(跑spfa时可行)，并且总的权值之和为负(不断地更新dist，直到有一点的序号超过总点数)；
注:从spfa中跳出的点并不是就是圈中的点，可能开始时就弄进去负边权，导致之后出圈了序号才大于点数；
ps: sb地竟然是一直MLE...，但是返回WA，图中的边数为n*n(没算源汇连边)..
#include<iostream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> #include<stack> #include<set> #include<map> #include<queue> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a) memset(a,-1,sizeof(a)) #define MSi(a) memset(a,0x3f,sizeof(a)) #define inf 0x3f3f3f3f #define lson l, m, rt << 1 #define rson m+1, r, rt << 1|1 typedef long long ll; #define A first #define B second #define MK make_pair typedef __int64 ll; template<typename T> void read1(T &m) { T x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} m = x*f; } template<typename T> void read2(T &a,T &b){read1(a);read1(b);} template<typename T> void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);} template<typename T> void out(T a) { if(a>9) out(a/10); putchar(a%10+'0'); } int T,kase = 1,i,j,k,n,m,s,t; const int M = 25007; const int N = 207; int head[M],tot; struct Edge{ int from,to,cap,Next,w; Edge(){} Edge(int f,int to,int cap,int w,int Next):from(f),to(to),cap(cap),Next(Next),w(w){} }e[M<<1]; inline void ins(int u,int v,int cap,int w) { e[++tot] = Edge{u,v,cap,w,head[u]}; head[u] = tot; } int dist[N][N]; struct data{int x,y,c;}X[N],Y[N]; void calc() { rep1(i,1,n) rep1(j,1,m) //这和之后的建图并不一样; dist[i][j] = abs(X[i].x - Y[j].x) + abs(X[i].y - Y[j].y) + 1; } int sum[N],ans[N][N]; int inq[N],d[N],num[N],p[N]; queue<int> Q; int spfa() { while(!Q.empty()) Q.pop(); MSi(d);MS0(inq);MS0(num); Q.push(t); inq[t] = 1;d[t] = 0;num[t] = 1; while(!Q.empty()){ int u = Q.front();Q.pop(); inq[u] = 0; for(int id = head[u];id;id = e[id].Next){ int v = e[id].to; if(d[v] > d[u] + e[id].w && e[id].cap){ //负圈的判定,所有圈中的边费用均为正，费用之和为负; d[v] = d[u] + e[id].w; p[v] = u; if(!inq[v]){ num[v] = num[u] + 1; if(num[v] > n+m+2) return v; Q.push(v);inq[v] = 1; } } } } return -1; } int solve() { int st = spfa(),u,v; if(st == -1){return puts("OPTIMAL"),0;} puts("SUBOPTIMAL"); MS0(inq); while(1){ if(!inq[st]) inq[st] = 1,st = p[st]; else{ v = st;break;} } do{ u = p[v]; if(u > n) ans[v][u-n]--;//正向边的费用为正，所以--将费用减少; else ans[u][v-n]++; v = u; }while(v != st); rep1(i,1,n){ printf("%d",ans[i][1]); rep1(j,2,m) printf(" %d",ans[i][j]); puts(""); } } int main() { while(scanf("%d%d",&n,&m) == 2){ MS0(head);tot = 1; rep1(i,1,n) read3(X[i].x,X[i].y,X[i].c); rep1(i,1,m) read3(Y[i].x,Y[i].y,Y[i].c); calc(); s = 0, t = n + m + 1; int w; rep1(i,1,n) rep1(j,1,m){ read1(w); ans[i][j] = w; ins(i,n+j,inf - w,dist[i][j]);//残余网络，但是边的权值没变 ins(n+j,i,w,-dist[i][j]);//原图中房子之间容量为inf和0； sum[j] += w; } rep1(i,1,n) ins(s,i,0,0), ins(i,s,X[i].c,0); rep1(j,1,m) ins(j+n,t,Y[j].c-sum[j],0), ins(t,j+n,sum[j],0); solve(); } return 0; }