题意抽象出来就是给了一个费用流的残存网络，判断该方案是不是最优方案，如果不是，还要求给出一个更优方案。
在给定残存网络上检查是否存在负环即可判断是否最优。
沿负环增广一轮即可得到更优方案。
考虑到制作模板的需要，我用前向星建图做的。此题用邻接矩阵应该更方便。
#include<queue> #include<cstdio> #include<algorithm> #include<cstring> #define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=220; const int MAXN=41000; int nbuild,nshelt; int x[maxn],y[maxn]; int tot,S,T; int pointer[maxn]; int toT[MAXN]; int flo[maxn][maxn]; const int INF=0x3f3f3f; int dis[maxn],pre[maxn],in[maxn],use[maxn]; bool vis[maxn]; bool visit[maxn]; struct Edge { int to,next,cap,f,w; Edge() {}; Edge(int b,int c,int nxt,int flow,int weight) {to=b,cap=c,next=nxt,f=flow,w=weight;} }edge[MAXN]; inline void addedge(int a,int b,int c,int flow,int w1) { edge[tot]=Edge(b,c,pointer[a],flow,w1); pointer[a]=tot++; edge[tot]=Edge(a,0,pointer[b],-flow,-w1); pointer[b]=tot++; } inline int cost(int a,int b) { return abs(x[a]-x[b])+abs(y[a]-y[b])+1; } void init() { int t; memset(pointer,-1,sizeof(pointer)); memset(visit,0,sizeof(vis)); tot=0; S=0;T=nbuild+nshelt+1; rep(i,1,nbuild) { scanf("%d%d%d",&x[i],&y[i],&t); addedge(S,i,t,t,0); } rep(i,nbuild+1,nbuild+nshelt) { scanf("%d%d%d",&x[i],&y[i],&t); toT[i]=tot; addedge(i,T,t,0,0); } int aedge; rep(i,1,nbuild) { rep(j,1,nshelt) { scanf("%d",&t); addedge(i,nbuild+j,INF,t,cost(i,nbuild+j)); // printf("%d-->%d w=%d ",i,nbuild+j,cost(i,nbuild+j)); flo[i][j]=t; aedge=toT[nbuild+j]; edge[aedge].f+=t; edge[aedge^1].f-=t; } } } int ve=0; void clearcircle() { memset(use,0,sizeof(use)); int enter; while(1) { use[ve]++; // printf("ve=%d ",ve); if(use[ve]>=2) {enter=ve;break;} ve=edge[pre[ve]^1].to; } int sub; do { sub=edge[pre[ve]^1].to; edge[pre[ve]].f+=1; edge[pre[ve]^1].f-=1; ve=sub; }while(ve!=enter); rep(i,1,nbuild) { for(int j=pointer[i];j!=-1;j=edge[j].next) { int v=edge[j].to; if(v>nbuild) flo[i][v-nbuild]=edge[j].f; } } } int searchcircle(int s) { queue<int> q; rep(i,S,T) { dis[i]=INF; vis[i]=0; pre[i]=-1; in[i]=0; } q.push(s); vis[s]=1; in[s]++;dis[s]=0; while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; // printf("%d dis[u]=%d ",u,dis[u]); for(int j=pointer[u];j!=-1;j=edge[j].next) { int v=edge[j].to; // printf("%d-->%d vis[v]=%d dis[v]=%d ds[u]=%d edge[j].w=%d ",u,v,vis[v],dis[v],dis[u],edge[j].w); if(edge[j].cap-edge[j].f&&dis[v]>dis[u]+edge[j].w) { dis[v]=dis[u]+edge[j].w; pre[v]=j; // printf("%d-->%d vis[v]=%d dis[v]=%d ds[u]=%d edge[j].w=%d ",u,v,vis[v],dis[v],dis[u],edge[j].w); if(!vis[v]) { vis[v]=1; visit[v]=1; in[v]++; q.push(v); if(in[v]>=T) { ve=v; return 1; } } } } } return 0; } int main() { // freopen("in.txt","r",stdin); while(scanf("%d",&nbuild)==1) { scanf("%d",&nshelt); init(); /*rep(i,1,nbuild) { rep(j,1,nshelt) printf("%d ",flo[i][j]); printf(" "); } rep(i,1,nbuild) { rep(j,1,nshelt) printf("%d ",cost(i,nbuild+j)); printf(" "); }*/ int flag=0; ve=0; rep(i,S,T) { if(visit[i]) continue; ve=searchcircle(i); if(ve) { flag=1; printf("SUBOPTIMAL "); clearcircle(); rep(i,1,nbuild) { rep(j,1,nshelt) printf("%d ",flo[i][j]); printf(" "); } break; } } if(!flag) printf("OPTIMAL "); } return 0; }