QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#116328 | #4776. Smoking gun | momoyuu | WA | 1ms | 3400kb | C++17 | 3.6kb | 2023-06-28 15:23:47 | 2023-06-28 15:23:51 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
template< typename flow_t >
struct Dinic {
const flow_t INF;
struct edge {
int to;
flow_t cap;
int rev;
bool isrev;
int idx;
};
vector< vector< edge > > graph;
vector< int > min_cost, iter;
Dinic(int V) : INF(numeric_limits< flow_t >::max()), graph(V) {}
void add_edge(int from, int to, flow_t cap, int idx = -1) {
graph[from].emplace_back((edge) {to, cap, (int) graph[to].size(), false, idx});
graph[to].emplace_back((edge) {from, 0, (int) graph[from].size() - 1, true, idx});
}
bool bfs(int s, int t) {
min_cost.assign(graph.size(), -1);
queue< int > que;
min_cost[s] = 0;
que.push(s);
while(!que.empty() && min_cost[t] == -1) {
int p = que.front();
que.pop();
for(auto &e : graph[p]) {
if(e.cap > 0 && min_cost[e.to] == -1) {
min_cost[e.to] = min_cost[p] + 1;
que.push(e.to);
}
}
}
return min_cost[t] != -1;
}
flow_t dfs(int idx, const int t, flow_t flow) {
if(idx == t) return flow;
for(int &i = iter[idx]; i < graph[idx].size(); i++) {
edge &e = graph[idx][i];
if(e.cap > 0 && min_cost[idx] < min_cost[e.to]) {
flow_t d = dfs(e.to, t, min(flow, e.cap));
if(d > 0) {
e.cap -= d;
graph[e.to][e.rev].cap += d;
return d;
}
}
}
return 0;
}
flow_t max_flow(int s, int t) {
flow_t flow = 0;
while(bfs(s, t)) {
iter.assign(graph.size(), 0);
flow_t f = 0;
while((f = dfs(s, t, INF)) > 0) flow += f;
}
return flow;
}
void output() {
for(int i = 0; i < graph.size(); i++) {
for(auto &e : graph[i]) {
if(e.isrev) continue;
auto &rev_e = graph[e.to][e.rev];
cout << i << "->" << e.to << " (flow: " << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl;
}
}
}
};
void solve(){
int n,m;
cin>>n>>m;
int h = n;int w = m;
Dinic<int> dinic(2*n*m+2);
int st = 2 * n * m;
int t = st + 1;
int a = 0;
int b = 0;
int dx[] = {1,-1,0,0};
int dy[] = {0,0,1,-1};
vector<string> s(n);
for(int i = 0;i<n;i++) cin>>s[i];
for(int i = 0;i<n;i++){
for(int j = 0;j<m;j++){
if(s[i][j]=='.') continue;
int ni = i * w + j;
if(s[i][j]=='W'){
a++;
dinic.add_edge(ni,t,1);
continue;
}
b++;
dinic.add_edge(st,ni,1);
dinic.add_edge(st,ni+n*m,1);
for(int k = 0;k<4;k++){
int nni = i + dx[k];
int nnj = j + dy[k];
if(nni<0||nni>=n||nnj<0||nnj>=m) continue;
if(s[nni][nnj]!='W') continue;
if(k<2) dinic.add_edge(ni,nni*w+nnj,1);
else dinic.add_edge(ni+n*m,nni*w+nnj,1);
}
}
}
int can = dinic.max_flow(st,t);
if(a==2*b&&can==a) cout<<"YES\n";
else cout<<"NO\n";
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
solve();
}
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3400kb
input:
3 4 2 BillyTheKid 0 0 Andy 10 0 John 19 0 Larry 20 0 Andy heard BillyTheKid firing before John Larry heard John firing before BillyTheKid 2 2 Andy 0 0 Beate 0 1 Andy heard Beate firing before Andy Beate heard Andy firing before Beate 3 1 Andy 0 0 Beate 0 1 Charles 1 3 Beate heard Andy firing before ...
output:
NO YES YES
result:
wrong answer 1st lines differ - expected: 'BillyTheKid John', found: 'NO'