#include #include #include #include #include #include using namespace std; typedef pair pii; vector > adj[102]; //next, flow, cap, ridx vector > path; const int ST = 100; const int ED = 101; const int dx [4] = {-1,-1,0,0}; const int dy [4] = {-1,+1,-1,+1}; int N,M; char G[13][13]; int level[102]; bool bfs() { queue q; memset(level,0,sizeof(level)); level[ST]=1; q.emplace(ST); while(q.size()) { int now = q.front(); q.pop(); for(auto [next,flow,cap,ridx] : adj[now]) { if(cap<=flow) continue; if(level[next]>0) continue; q.emplace(next); level[next] = level[now] + 1; } } return level[ED] > 0; } bool dfs(int now) { if(now == ED) return true; for(auto [next,flow,cap,ridx] : adj[now]) { if(level[next] != level[now]+1) continue; if(cap <= flow) continue; path.emplace_back(next,flow,cap,ridx); if(dfs(next)) return true; path.pop_back(); } return false; } void solve() { int cnt=0; vector in; scanf("%d %d",&N,&M); for(int i=0;i=N || nj<0 || nj>=M) continue; if(G[ni][nj]=='x') continue; int num = M*i + j, nnum = M*ni + nj; in.emplace_back(min(num,nnum),max(num,nnum)); } } } sort(in.begin(),in.end()); in.erase(unique(in.begin(),in.end()),in.end()); for(auto [u,v] : in) // u <= v { if(v == ST) { adj[u].emplace_back(v,0,0,adj[v].size()); adj[ST].emplace_back(u,0,1,adj[u].size()-1); } else if (v==ED) { adj[u].emplace_back(v,0,1,adj[v].size()); adj[ED].emplace_back(u,0,0,adj[u].size()-1); } else { // odd is right side if(u&1) swap(u,v); adj[u].emplace_back(v,0,1,adj[v].size()); adj[v].emplace_back(u,0,0,adj[u].size()-1); } } int ans=0; while(1) { if(!bfs()) break; while(1) { path.clear(); if(!dfs(ST)) break; int mn = 2e9; for(auto [next,flow,cap,ridx] : path) mn = min(mn,cap-flow); ans += mn; int now = ST; for(auto [next,flow,cap,ridx] : path) { int idx = get<3>(adj[next][ridx]); get<2>(adj[next][ridx])+=mn; get<1>(adj[now][idx])+=mn; now = next; } } } printf("%d\n",cnt-ans); } int main() { int tc; scanf("%d",&tc); while(tc--) solve(); }

제출 #110853

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: