题意：给一个n*m的矩形，往每个格子填0-k的数字，使得对第i行和为row[i]，第i列和为col[i]，问是否存在方案，方案是否唯一，如果方案唯一则输出具体方案。

思路：首先根据问题提取对象，行、列、格子、数，只有数可以连接其它的对象。从源点向第i行连一条容量为row[i]的有向边，从第i行向第i行的每个格子连一条容量为k的有向边，从每个格子向第i列（i为格子的列号）连一条容量为k的有向边，然后从第i列向汇点连一条容量为col[i]的边。这样建图以后，发现每个格子唯一连接一个行和一个列，也就是入度和出度均为1，那么格子其实就没有存在的必要了，直接从每行向每列连一条容量为k的有向边。如果最大流=Σrow[i]=Σcol[i]，则表明有解。对于有多解的情况，只需判断残量网络是否存在有向环，因为在环上增减流量能得到不同的解而最大流不变。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
/* ******************************************************************************** */
#include <iostream>                                                                 //
#include <cstdio>                                                                   //
#include <cmath>                                                                    //
#include <cstdlib>                                                                  //
#include <cstring>                                                                  //
#include <vector>                                                                   //
#include <ctime>                                                                    //
#include <deque>                                                                    //
#include <queue>                                                                    //
#include <algorithm>                                                                //
#include <map>                                                                      //
using namespace std;                                                                //
                                                                                    //
#define pb push_back                                                                //
#define mp make_pair                                                                //
#define X first                                                                     //
#define Y second                                                                    //
#define all(a) (a).begin(), (a).end()                                               //
#define foreach(a, i) for (typeof(a.begin()) i = a.begin(); i != a.end(); ++ i)     //
#define fill(a, x) memset(a, x, sizeof(a))                                          //
                                                                                    //
void RI(vector<int>&a,int n){a.resize(n);for(int i=0;i<n;i++)scanf("%d",&a[i]);}    //
void RI(){}void RI(int&X){scanf("%d",&X);}template<typename...R>                    //
void RI(int&f,R&...r){RI(f);RI(r...);}void RI(int*p,int*q){int d=p<q?1:-1;          //
while(p!=q){scanf("%d",p);p+=d;}}void print(){cout<<endl;}template<typename T>      //
void print(const T t){cout<<t<<endl;}template<typename F,typename...R>              //
void print(const F f,const R...r){cout<<f<<", ";print(r...);}template<typename T>   //
void print(T*p, T*q){int d=p<q?1:-1;while(p!=q){cout<<*p<<", ";p+=d;}cout<<endl;}   //
                                                                                    //
typedef pair<int, int> pii;                                                         //
typedef long long ll;                                                               //
typedef unsigned long long ull;                                                     //
                                                                                    //
template<typename T>bool umax(T&a, const T&b){return b>a?false:(a=b,true);}         //
template<typename T>bool umin(T&a, const T&b){return b<a?false:(a=b,true);}         //
template<typename T>                                                                //
void V2A(T a[],const vector<T>&b){for(int i=0;i<b.size();i++)a[i]=b[i];}            //
template<typename T>                                                                //
void A2V(vector<T>&a,const T b[]){for(int i=0;i<a.size();i++)a[i]=b[i];}            //
                                                                                    //
/* -------------------------------------------------------------------------------- */
 
 
struct Dinic {
private:
    const static int maxn = 800 + 7;
    struct Edge {
        int from, to, cap;
        Edge(int u, int v, int w): from(u), to(v), cap(w) {}
    };
    int s, t;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool vis[maxn];
    int d[maxn], cur[maxn];
 
    bool bfs() {
        memset(vis, 0, sizeof(vis));
        queue<int> Q;
        Q.push(s);
        d[s] = 0;
        vis[s] = true;
        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) {
                    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[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap))) > 0) {
                e.cap -= f;
                edges[G[x][i] ^ 1].cap += f;
                flow += f;
                a -= f;
                if (a == 0) break;
            }
        }
        return flow;
    }
 
public:
    void clear() {
        for (int i = 0; i < maxn; i ++) G[i].clear();
        edges.clear();
        memset(d, 0, sizeof(d));
    }
    void add(int from, int to, int cap) {
        edges.push_back(Edge(from, to, cap));
        edges.push_back(Edge(to, from, 0));
        int m = edges.size();
        G[from].push_back(m - 2);
        G[to].push_back(m - 1);
    }
 
    int solve(int s, int t) {
        this->s = s; this->t = t;
        int flow = 0;
        while (bfs()) {
            memset(cur, 0, sizeof(cur));
            flow += dfs(s, 1e9);
        }
        return flow;
    }
    bool FC(int fa, int rt) {
        vis[rt] = true;
        int sz = G[rt].size();
        for (int i = 0; i < sz; i ++) {
            Edge &e = edges[G[rt][i]];
            if (e.to != fa && e.cap) {
                if (vis[e.to]) return true;
                if (FC(rt, e.to)) return true;
            }
        }
        vis[rt] = false;
        return false;
    }
    bool get(int n, int m) {
        memset(vis, 0, sizeof(vis));
        for (int i = 1; i <= n; i ++) {
            if (FC(-1, i)) return true;
        }
        return false;
    }
    void out(int n, int m) {
        int now = n * 2 + m * 2 + 1;
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < m; j ++) {
                printf("%d%c", edges[now].cap, j == m - 1? '\n' : ' ');
                now += 2;
            }
        }
    }
};
Dinic solver;
const int maxn = 407;
int row[maxn], col[maxn];
 
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int n, m, k;
    while (cin >> n >> m >> k) {
        solver.clear();
        int total = 0;
        for (int i = 1; i <= n; i ++) {
            int x;
            RI(x);
            solver.add(0, i, x);
            total += x;
        }
        for (int i = 1; i <= m; i ++) {
            int x;
            RI(x);
            solver.add(n + i, n + m + 1, x);
        }
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= m; j ++) {
                solver.add(i, n + j, k);
            }
        }
        int flow = solver.solve(0, n + m + 1);
        if (flow != total) puts("Impossible");
        else {
            if (solver.get(n, m)) puts("Not Unique");
            else {
                puts("Unique");
                solver.out(n, m);
            }
        }
    }
    return 0;                                                                       //
}                                                                                   //
                                                                                    //
                                                                                    //
                                                                                    //
/* ******************************************************************************** */

最新文章

  1. 跟着思维导图学习javascript
  2. 理解flex_对齐
  3. LGLAlertView 提示框
  4. [转]Windows网络编程学习-面向连接的编程方式
  5. MySQL: 详细的sql语句
  6. Unity3D ShaderLab 布料着色器
  7. Spark学习笔记--概念知识
  8. Eclipse 实现关键字自动补全功能 （转）
  9. 【FBA】SharePoint 2013自定义Providers在基于表单的身份验证（Forms-Based-Authentication）中的应用
  10. LINUX 笔记-iostat命令
  11. javascript参数传递中处理+号
  12. AI-2.梯度下降算法
  13. leetcode 224. Basic Calculator 、227. Basic Calculator II
  14. SQLServer 关于 HAVING子句
  15. composer lavarel 安装
  16. Python实现机器学习算法：AdaBoost算法
  17. Chargen UDP服务远程拒绝服务攻击漏洞修复教程
  18. 在Ubuntu下利用Eclipse调试FFmpeg《转》
  19. MORMOT的数据序列
  20. 【BZOJ】【3339】Rmq Problem

热门文章

  1. 基于scrapy框架输入关键字爬取有关贴吧帖子
  2. jmeter引入外部jar包的方法
  3. 负载均衡服务之HAProxy基础配置（二）
  4. Jmeter系列（3）- Jmeter安装目录介绍
  5. docker 搭建一个wordpress 博客系统（4）
  6. 为什么要你们现在要学习python
  7. CTR学习笔记&amp;代码实现4-深度ctr模型 NFM/AFM
  8. vue + ArcGIS 地图应用系列一：arcgis api本地部署(开发环境)
  9. 每天认识几个HTTP 响应码
  10. CentOS7编译安装NodeJS