建立某个时间段的残量网络，然后用消圈算法检测是否有负环 初始图是这么建的： 1.s到每个建筑的建边，容量是每个建筑的人，费用是0 2.每个建筑到每个避难所建边，容量是inf，费用是距离 3.避难所到t建边，容量是避难所的容量，费用是0 现在给定了一些建筑的人所在的避难所，等价于给出了一些增广路 那么只要把这些增广路加在初始图上，做出残量网络即可 1.s到所有建筑必定满流，所以不用考虑特殊情况，只要建立i->s的边即可 2.建筑到避难所原图上容量是inf，所以只要建立i->j,权值为距离 3.建筑i到避难所j有流量，那么残量网络j->i必定有流，权值为负距离 4.避难所j中的人数大于0，说明残量网络上t->j必定有流，权值为0 5.避难所没有满，说明残量网络上j->t必定有流，权值为0 在残量网络上找负圈，然后取负圈上两点，正向边+1，反向边-1
自己写的代码怎么都调不出来。。先放网上的记一下
#include <iostream> #include <cstring> #include <cmath> #include <algorithm> #include <string.h> #include <string> #include <vector> #include <queue> #define MEM(a,x) memset(a,x,sizeof a) #define eps 1e-8 #define MOD 10009 #define INF 100000000 #define ll __int64 #define bug cout<<"here"<<endl #define fread freopen("ceshi.txt","r",stdin) #define fwrite freopen("out.txt","w",stdout) using namespace std; struct Edge { int to,next,cost; }edge[100000]; int n,m; int head[300],tol; void addedge(int u,int v,int cost) { edge[tol].to=v; edge[tol].cost=cost; edge[tol].next=head[u]; head[u]=tol++; } int x[110][3],y[110][3],sum[110],ans[110][110]; int pre[300],vis[300],num[300],dis[300]; //pre记录负环，num入队列的次数,spfa返回最先入队>n的点 int len[110][110]; int spfa(int s,int n) { queue<int> q; MEM(vis,0); MEM(num,0); for(int i=0;i<n;i++) dis[i]=INF; q.push(s); vis[s]=1; num[s]++; dis[s]=0; while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(dis[u]+edge[i].cost<dis[v]) { dis[v]=dis[u]+edge[i].cost; pre[v]=u; if(!vis[v]) { vis[v]=1; q.push(v); if(++num[v]>n) return v; } } } } return -1; } int main() { // fread; // int n,m; while(scanf("%d%d",&n,&m)!=EOF) { for(int i=0;i<n;i++) scanf("%d%d%d",&x[i][0],&x[i][1],&x[i][2]); for(int i=0;i<m;i++) scanf("%d%d%d",&y[i][0],&y[i][1],&y[i][2]); MEM(head,-1); tol=0; int s=n+m;//汇点 for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { len[i][j]=abs(x[i][0]-y[j][0])+abs(x[i][1]-y[j][1])+1; addedge(i,j+n,len[i][j]); } } MEM(sum,0); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { scanf("%d",&ans[i][j]); if(ans[i][j]!=0) addedge(j+n,i,-len[i][j]); sum[j]+=ans[i][j]; } } for(int i=0;i<m;i++) { if(sum[i]<y[i][2]) addedge(i+n,s,0); if(sum[i]>0) addedge(s,i+n,0); } int id=spfa(s,s+1); if(id==-1) puts("OPTIMAL"); else { puts("SUBOPTIMAL"); int st=id; MEM(vis,0); while(1) { if(!vis[st]) { vis[st]=1; st=pre[st]; } else { id=st; break; } } do { int u=pre[st],v=st; if(u<n&&v>=n&&v<s) ans[u][v-n]++; if(v<n&&u>=n&&u<s) ans[v][u-n]--; st=pre[st]; }while(st!=id); for(int i=0;i<n;i++) { printf("%d",ans[i][0]); for(int j=1;j<m;j++) printf(" %d",ans[i][j]); puts(""); } } } return 0; }