天才钱vs学霸周2
Time Limit: 500 MS Memory Limit: 128 MB
Submit Status
由于上次的游戏中学霸周输了，因此学霸周想出个问题为难天才钱，问题是这样的，有一个n×mn×m的矩阵，每一个格子中有一个整数，周大爷给出了数组A[1⋯n]A[1⋯n](A[i]A[i]表示第ii行的元素之和)以及数组B[1⋯m]B[1⋯m] (B[i]B[i]表示第ii列的元素之和)，现在周大爷问钱大爷能否给每个格子(i,j)(i,j)填一个整数p[i][j]p[i][j]（1≤p[i][j]≤201≤p[i][j]≤20）使得满足周大爷一开始给出的两个数组。钱大爷觉得暴力都可以啊，所以他不想解决这么easy的问题。现在，他决定把问题交给你。
Input
第一行两个整数nn，mm（1≤n,m≤201≤n,m≤20）
第二行n个整数表示A[1⋯n]A[1⋯n]（m≤A[i]≤20×mm≤A[i]≤20×m）
第三行m个整数表示B[1⋯m]B[1⋯m] （n≤B[i]≤20×nn≤B[i]≤20×n）
Output
如果能构造出来合法的矩阵输出“Yes”，并换行输出一个n×mn×m的合法矩阵KK，满足数组A[1⋯n]A[1⋯n]，B[1⋯m]B[1⋯m]的要求并且1≤K[i][j]≤201≤K[i][j]≤20,反之输出“No”。
Sample input and output
| Sample Input | Sample Output |
|---|---|
2 2 2 2 2 2 | Yes 1 1 1 1 |
1 1 1 2 | No |
Hint
样例不等于test1
Source
2018 UESTC ACM Training for Graph Theory
题解：刘汝佳老师白书上有解释，不过没代码Orz... 我们可以利用网络流来解决。建立超级源点s，超级汇点t;s与每一行的和建立一条容量为每一行的和的边，t与每一列的和建立一条容量为每一行的和的边，然后对于每一行的与每一列的和分别建立一条容量为19的边（因为流量可以为零，我们可以让每个和减一，因为最大的数不超过20，所以为19）； 然后寻找增广路，加流量直到没有增广路，如果可以做到没有增广路，这有解，否则无解 。
AC代码为：
#include<iostream> #include<queue> #include<cstring> #include<cstdio> #define maxn 1000 #define INF 0x3f3f3f3f using namespace std; struct Edge { int from,to,cap,flow;// 顾名思义 from to 容量 流量 Edge(int u,int v,int c,int f): from(u),to(v),cap(c),flow(f) {} }; struct Dinic { int n,m,s,t; vector<Edge> edges; vector<int> G[maxn]; int d[maxn]; int cur[maxn]; bool vis[maxn]; void init(int n) { for (int i=0; i<n; i++) G[i].clear(); edges.clear(); } void Addedge(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); } bool BFS() { // 建立分层图 memset(vis,false,sizeof(vis)); for (int i=0; i<n; i++) d[i] = INF; d[s] = 0; vis[s] = true; queue<int> Q; Q.push(s); while (!Q.empty()) { int x = Q.front(); Q.pop(); for (int i=0; i<G[x].size(); i++) { Edge e = edges[G[x][i]]; if (!vis[e.to] && e.cap>e.flow) { vis[e.to] = true; d[e.to] = d[x]+1; Q.push(e.to); } } } return vis[t]; } int DFS(int x,int a) { // 当前弧优化 if (x == t || a == 0) return a; int flow = 0,f; for (int i=cur[x]; i<G[x].size(); i++) { Edge& e = edges[G[x][i]]; if (d[e.to] == d[x]+1 && (f = DFS(e.to,min(a,e.cap-e.flow))) > 0) { e. flow += f; edges[G[x][i]^1].flow -= f;// 反边减去f flow += f; a -= f; if (a == 0) break; } } return flow; } bool OKA() { // 判断是否满流 for (int i=0; i<G[s].size(); i++) { Edge e = edges[G[s][i]]; if (e.cap!=e.flow) return false; } return true; } bool OKB(int R,int C) { for (int j=R+1; j<=R+C; j++) { Edge& e = edges[G[j][0]]; if (e.cap!=e.flow) return false; } return true; } void Maxflow(int R,int C) { int flow = 0; // while (BFS()) { memset(cur,0,sizeof(cur)); flow += DFS(s,INF); } // //return flow;//最大流 if (OKA()&&OKB(R,C) ) { cout<<"Yes"<<endl; for (int i=1; i<=R; i++) { int j; for (j=1; j<G[i].size()-1; j++) cout<<edges[G[i][j]].flow+1<<' '; cout<<edges[G[i][j]].flow+1<<endl; } } else { cout<<"No"<<endl; } cout<<endl; } }; int main() { Dinic aa;// 统一放在结构体中 int T,R,C,tmp; int a[30],b[30],c[30],d[30]; aa.init(maxn); scanf("%d%d",&R,&C); for (int i=1; i<=R; i++) cin>>a[i]; for (int i=1; i<=C; i++) cin>>b[i]; for (int i=1; i<=R; i++) c[i] = a[i]-C; for (int i=1; i<=C; i++) d[i] = b[i]-R; for (int i=1; i<=R; i++) aa.Addedge(0,i,c[i]);// 源点s 建边 for (int i=1; i<=C; i++) aa.Addedge(R+i,R+C+1,d[i]);// 汇点 t 建边 for (int i=1; i<=R; i++) for (int j=1; j<=C; j++) aa.Addedge(i,R+j,19); aa.s = 0; aa.t = R+C+1; aa.Maxflow(R,C); return 0; }