CodeForces 546E - Soldier and Traveling（最大流）-白红宇

CodeForces 546E - Soldier and Traveling（最大流）

阅读量：4647 次

发布时间：2019-06-09

本文共 1835 字，大约阅读时间需要 6 分钟。

题目链接

【题意】

给定一张n个结点，m条边的无向图，再给定n个整数a[1],a[2]…a[n]代表初始时每个结点上驻守的士兵数量，每个结点的士兵可以在原地不动，也可以移动到与当前结点邻接的其他结点上去，但只能移动一次。现在问，能否通过合理的移动使得最终这n个结点驻守的士兵数量分别为b[1],b[2]…b[n]，如果可以输出”YES”，同时输出一个矩阵表示士兵的移动情况，矩阵的第u行第v列代表有多少个士开始在u结点，后来到了v结点，如果无解输出”NO”即可。

【思路】

类似这样的多种初始状态的问题要往网络流的算法上想，关键问题在于建立最大流模型，这道题应该这样建模，首先建立一个下标为0的源点和下标为n*2+1的汇点，然后把原来图中的每个结点u拆分成两个点，u和u+n，然后连接一条(u,u+n,inf)的有向边，代表士兵可以原地不动，同时把源点到各个点连接一条有向边(0,u,a[u])代表初始状态，同时连接各个点到汇点一条有向边(u,n*2+1,b[u])表示最后的状态，然后跑最大流算法，如果最大流的值等于数组a的总和和数组b的总和，那就说明问题有解，否则无解。有个坑点是题目不保证数组a,b的和相同。

#include
    
     using namespace std;const int inf=2e9;const int maxn=220;struct Edge{    int from,to,cap,flow;    Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}};struct EdmondsKarp{    int n,m;    vector
     
       edges;    vector
      
        g[maxn];    int a[maxn];    int p[maxn];    void init(int n){        this->n=n;        for(int i=0;i

que; que.push(s); a[s]=inf; while(!que.empty()){ int x=que.front(); que.pop(); for(int i=0;i

e.flow){ p[e.to]=g[x][i]; a[e.to]=min(a[x],e.cap-e.flow); que.push(e.to); } } if(a[t]) break; } if(!a[t]) break; for(int u=t;u!=s;u=edges[p[u]].from){ edges[p[u]].flow+=a[t]; edges[p[u]^1].flow-=a[t]; } flow+=a[t]; } return flow; }};int n,m;int a[maxn],b[maxn];int suma,sumb;int ans[maxn][maxn];EdmondsKarp ek;void solve(){ if(suma==sumb && ek.maxflow(0,n*2+1)==suma){ puts("YES"); for(int u=1;u<=n;++u){ for(int j=0;j

0) ans[u][v]=e.flow; } } for(int i=1;i<=n;++i){ for(int j=1;j<=n;++j) printf("%d%c",ans[i][j],j==n?'\n':' '); } } else puts("NO");}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) { scanf("%d",&a[i]); suma+=a[i]; } for(int i=1;i<=n;++i) { scanf("%d",&b[i]); sumb+=b[i]; } ek.init(n*2+2); for(int i=1;i<=n;++i){ ek.add(i,i+n,inf); ek.add(0,i,a[i]); ek.add(i+n,n*2+1,b[i]); } for(int i=0;i

转载于:https://www.cnblogs.com/wafish/p/10465323.html

你可能感兴趣的文章