链接 ：?id=36866
可以建一个类似二分图，X集合是所有行，Y集合是所有列，X->Y的容量为（1到20）。建立源点连接每个X中的点，容量为该行的和。建立汇点连接Y中的点，容量为该行的列。目的是求从源点出发的流量就是容量，且必须走完所有流量并到达汇点，汇点的流量必须是源点发出的流量。这样控制路径后求出中间过程的流量各式多少。
因为题目规定了每行的和必须等于给定的数，所以从原点出发的必须是满流，到达汇点的流也是满流。由于直接计算会出现有些流量为0的情况不满足大于等于1小于等于20，所以可以一开始处理对整张图的点都减1 最后再加1。
/*——————— #headfile——————–*/#include <algorithm>#include <iostream>#include <sstream>#include <cstring>#include <cstdlib>#include <cassert>#include <cstdio>#include <vector>#include <cmath>#include <queue>#include <stack>#include <set>#include <map>/*———————-#define———————-*/#define DRII(X,Y) int (X),(Y);scanf("%d%d",&(X),&(Y))#define EXP 2.7182818284590452353602874713527#define CASET int _;cin>>_;while(_–)#define RII(X, Y) scanf("%d%d",&(X),&(Y))#define DRI(X) int (X);scanf("%d", &X)#define mem(a,b) memset(a,b,sizeof(a))#define rep(i,n) for(int i=0;i<n;i++)#define ALL(X) (X).begin(),(X).end()#define INFL 0x3f3f3f3f3f3f3f3fLL#define RI(X) scanf("%d",&(X))#define SZ(X) ((int)X.size())#define PDI pair<double,int>#define rson o<<1|1,m+1,r#define PII pair<int,int>#define MAX 0x3f3f3f3f#define lson o<<1,l,m#define MP make_pair#define PB push_back#define SE second#define FI firsttypedef long long ll;template<class T>T MUL(T x,T y,T P){T F1=0;while(y){if(y&1){F1+=x;if(F1<0||F1>=P)F1-=P;}x<<=1;if(x<0||x>=P)x-=P;y>>=1;}return F1;}template<class T>T POW(T x,T y,T P){T F1=1;x%=P;while(y){if(y&1)F1=MUL(F1,x,P);x=MUL(x,x,P);y>>=1;}return F1;}template<class T>T gcd(T x,T y){if(y==0)return x;T z;while(z=x%y)x=y,y=z;return y;}#define DRIII(X,Y,Z) int (X),(Y),(Z);scanf("%d%d%d",&(X),&(Y),&(Z))#define RIII(X,Y,Z) scanf("%d%d%d",&(X),&(Y),&(Z))const double pi = acos(-1.0);const double eps = 1e-6;const ll mod = 1000000007ll;const int M = 100005;const int N = 205;using namespace std;/*———————-Main————————-*/struct Edge {int to, c, rev;Edge() {}Edge(int _to, int _c, int _rev) {to = _to, c = _c, rev = _rev;}};vector<Edge> G[N];int lv[N], iter[N];void add(int from, int to, int c) {G[from].PB( Edge(to, c, SZ(G[to])) );G[to].PB( Edge(from, 0, SZ(G[from]) – 1) );}void BFS(int s) {mem(lv, -1);queue<int> q;lv[s] = 0;q.push(s);while(!q.empty()) {int v = q.front(); q.pop();for(int i = 0; i < SZ(G[v]); i++) {Edge &e = G[v][i];if(e.c > 0 && lv[e.to] < 0) {lv[e.to] = lv[v] + 1;q.push(e.to);}}}}int dfs(int v, int t, int f) {if(v == t) return f;for(int &i = iter[v]; i < SZ(G[v]); i++) {Edge &e = G[v][i];if(e.c > 0 && lv[v] < lv[e.to]) {int d = dfs(e.to, t, min(f, e.c));if(d > 0) {e.c -= d;G[e.to][e.rev].c += d;return d;}}}return 0;}int MF(int s, int t) {int res = 0;for(;;) {BFS(s);if(lv[t] < 0) return res;mem(iter, 0);int f;while((f = dfs(s, t, 1e9)) > 0) {res += f;}}}int n, m, FF = 0;int A[N], B[N], a[N], b[N];void solve() {if(FF) puts(""); FF++;RII(n, m);for(int i = 0; i <= n + m + 1; i++) G[i].clear();for(int i = 1; i <= n; i++) {RI(A[i]);a[i] = A[i] – A[i-1];}for(int i = 1; i <= m; i++) {RI(B[i]);b[i] = B[i] – B[i-1];}int s = 0, t = n + m + 1;for(int i = 1; i <= n; i++) {add(s, i, a[i] – m);}for(int i = 1; i <= m; i++) {add(i + n, t, b[i] – n);}for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {add(i, j + n, 19);}}int ans = MF(0, n + m + 1) + n * m;assert(ans == A[n]);assert(ans == B[m]);printf("Matrix %d\n", FF);for(int i = 1; i <= n; i++) {for(int j = 1; j < SZ(G[i]); j++) {Edge e = G[i][j];printf("%d%c", G[e.to][e.rev].c + 1, j == SZ(G[i]) – 1 ? '\n' : ' ');}}}int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);CASETsolve();return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
，不要忘本，任何时候，任何事情。
