QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#729085 | #7857. (-1,1)-Sumplete | nekoyellow | TL | 20ms | 12184kb | C++23 | 2.9kb | 2024-11-09 16:28:12 | 2024-11-09 16:28:15 |
Judging History
answer
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const char nl = '\n';
class MF {
public:
MF(int _n, int _s, int _t): n(_n), s(_s), t(_t) {
head.assign(n, -1); dep.resize(n);
}
void addedge(int u, int v, int w) {
e.push_back({v, head[u], w, 0}); head[u] = e.size()-1;
e.push_back({u, head[v], 0, 0}); head[v] = e.size()-1;
}
ll dinic() {
ll maxflow = 0;
while (bfs()) cur = head, maxflow += dfs(s, inf);
return maxflow;
}
static const int inf = numeric_limits<int>::max();
int n, s, t;
struct Edge { int v, nxt, c, f; };
vector<Edge> e; vector<int> head;
vector<int> dep, cur;
bool bfs() {
queue<int> q; q.push(s);
fill(dep.begin(), dep.end(), 0); dep[s] = 1;
while (q.size()) {
int u = q.front(); q.pop();
for (int i = head[u]; ~i; i = e[i].nxt) {
int v = e[i].v;
if (!dep[v] && e[i].c > e[i].f) q.push(v), dep[v] = dep[u]+1;
}
}
return dep[t];
}
int dfs(int u, int flow) {
if (u == t || !flow) return flow;
int ret = 0;
for (int &i = cur[u]; ~i; i = e[i].nxt) {
int v = e[i].v;
if (dep[v] == dep[u]+1) {
int d = dfs(v, min(flow-ret, e[i].c-e[i].f));
if (!d) continue;
e[i].f += d, e[i^1].f -= d; ret += d;
if (ret == flow) break;
}
}
return ret;
}
};
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int n;
cin >> n;
vector<string> g(n);
for (auto &s: g)
cin >> s;
vector<int> r(n), c(n);
for (auto &e: r)
cin >> e;
for (auto &e: c)
cin >> e;
if (n == 1 && r[0] != c[0]) {
cout << "No\n";
return 0;
}
int s = 2*n, t = 2*n+1;
MF mf(t+1, s, t);
ll ans = 0;
for (int i = 0; i < n; i++) {
if (r[i] > 0) ans += r[i];
r[i] >= 0 ? mf.addedge(s, i, r[i]) : mf.addedge(i, t, -r[i]);
for (int j = 0; j < n; j++) {
g[i][j] == '+' ? mf.addedge(i, n+j, 1) : mf.addedge(n+j, i, 1);
}
}
for (int j = 0; j < n; j++) {
if (c[j] < 0) ans -= c[j];
c[j] >= 0 ? mf.addedge(n+j, t, c[j]) : mf.addedge(s, n+j, -c[j]);
}
ll maxflow = mf.dinic();
if (ans != maxflow) {
cout << "No\n";
} else {
cout << "Yes\n";
vector<string> a(n, string(n, '0'));
for (int i = 0; i < n; i++) {
for (auto k = mf.head[i]; ~k; k = mf.e[k].nxt) {
int j = mf.e[k].v;
if (j == s || j == t) continue;
if (mf.e[k].f) a[i][j-n] = '1';
}
}
for (auto &s: a)
cout << s << '\n';
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 3452kb
input:
3 +-+ -++ +-+ 1 1 1 1 -1 3
output:
Yes 001 001 111
result:
ok n=3
Test #2:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
3 --- -++ +++ -2 -1 0 -2 -1 0
output:
Yes 110 100 000
result:
ok n=3
Test #3:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
3 +-+ -++ ++- 1 0 2 2 2 -1
output:
No
result:
ok n=3
Test #4:
score: 0
Accepted
time: 0ms
memory: 3784kb
input:
1 - -1 1
output:
No
result:
ok n=1
Test #5:
score: 0
Accepted
time: 0ms
memory: 3576kb
input:
1 - 0 0
output:
Yes 0
result:
ok n=1
Test #6:
score: 0
Accepted
time: 0ms
memory: 3884kb
input:
20 +-------+-----+++-++ -+-++++----++-++-++- -+++--+---+--+-++--- -+++-+--+----++---+- +++-+-++++++-+-+---+ -++-----+----++++++- +-++--+++++-++-+---- +-+----+---+-+++--+- +++++-+++++----+--+- ------++++---+--++-- ++++--------++++--+- -+-+-++++-+-++-++--+ ---+-++---+-++-++--- +-++++-++----+-+++-- +-+...
output:
Yes 00000000010000000100 00000000000010100010 00000000010000000100 00000011010000000100 00100000100101010001 00000000010000000000 00000000000101000101 00000000000000000001 00000000000000000000 00000100001100000001 00000001011100000101 00000000000101001000 10000000000001011000 00000000000001011000 00...
result:
ok n=20
Test #7:
score: 0
Accepted
time: 0ms
memory: 3852kb
input:
100 ++++-+-+--++++++-+--+--++-+-+--+++++-+++---+-+-+-++-+-+++-------+-++--+-++--+--+++++-++-+---+--+--++ -++--++-+-++++-+---++-+-+-+-+-+-+-+-+--+-+--+--+++---+--+-----+-----+-++-++-+-++++++--+-+++-+++-++++ --+---++-++--++-+++-------+--+-++------+-----+--+----++++++++-+--+++++--++--+-+-+++---+--+++-+...
output:
Yes 1111010100111111010010011010100010100000000000000000000000000000000000000000000011110110100010010011 0110011010111101000110101010100010100000000000000000000000000000000000000000101111110010111011101111 0010001101100110111000000010010010000000000000000000000000000000000000000000001011100010011101...
result:
ok n=100
Test #8:
score: 0
Accepted
time: 20ms
memory: 12184kb
input:
500 --+-+-+-++-----+++--+-+++-+---+-+-------+++--++++++-+--++--+-+-++++-++++--++--+---++--++----++--+---++-++--+-----+-+---++-++++-+++++++---++-++--+-++++-+----++-+++-+++---+--+++-+--++-++--+++++++-+++--+---+---+-+---++-+-+--+-+++-++-----+++-++-+++-+-++--++++++-+-++-+++---++-+++-++----+--+++----++++...
output:
Yes 11010101001111100011010001011101011111110001100000010110011010100001000011001101110011001111001101110010011011111010111001000010000000111001001101000010111100100010001110110001010001001100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
result:
ok n=500
Test #9:
score: -100
Time Limit Exceeded
input:
4000 -++-+-+-+--+-++++---+-++------++---+-+++--+++--+++++++---+-++-+++++++----+---+++-++--++---+-++--+----+---+--++-+-+-+-----+-+---++-++--+---+++-++++-+-----++--++-++---++-+--+++-+--+--+-+-++-+++--++---+++-+-+---+++-++-+-++-+-+++---+++---+-+--++---+-+---+--+++--+----+-+--++---+-----+-+--+----+-+++-...