CodeForces 546E - Soldier and Traveling（最大流）
题目链接 https://cn.vjudge.net/problem/CodeForces-546E
【题意】
给定一张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<bits/stdc++.h>
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<Edge> edges;
vector<int> g[maxn];
int a[maxn];
int p[maxn];
void init(int n){
this->n=n;
for(int i=0;i<n;++i) g[i].clear();
edges.clear();
}
void add(int from,int to,int cap){
edges.push_back(Edge(from,to,cap,0));
edges.push_back(Edge(to,from,0,0));
m=edges.size();
g[from].push_back(m-2);
g[to].push_back(m-1);
}
int maxflow(int s,int t){
int flow=0;
while(1){
memset(a,0,sizeof(a));
queue<int> que;
que.push(s);
a[s]=inf;
while(!que.empty()){
int x=que.front();
que.pop();
for(int i=0;i<g[x].size();++i){
Edge& e=edges[g[x][i]];
if(!a[e.to] && e.cap>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<ek.g[u].size();++j){
Edge& e=ek.edges[ek.g[u][j]];
int v=e.to-n;
if(1<=v && v<=n && e.flow>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<m;++i){
int u,v;
scanf("%d%d",&u,&v);
ek.add(u,v+n,inf);
ek.add(v,u+n,inf);
}
solve();
return 0;
}1、纯手工 CheckboxTree 实现
2、JAVA RMI远程方法调用简单实例（转载）
3、从程序员到项目经理（24）：怎样给领导汇报工作
4、基于Visual C++2010 与office2010开发办公自动化(22)- 动态创建播放幻灯片
5、也谈协方差矩阵