#include <bits/stdc++.h>
using namespace std;
struct Edge{
int u,v;
long long cap,flow;
Edge(){}
Edge(int u, int v, long long cap): u(u), v(v), cap(cap),flow(0){}
};
struct Dinic{
int N; ///number of nodes in the maxflow graph
vector<Edge> E;
vector<vector<int> > g;
vector<int> d,pt;
Dinic(int N): N(N),E(0),g(N),d(N),pt(N){}
///add edge going from "u" to "v" with capacity "cap"
void addEdge(int u, int v, long long cap){
if (u != v){
E.emplace_back(u,v,cap);
g[u].emplace_back(E.size()-1);
E.emplace_back(v,u,0);
g[v].emplace_back(E.size()-1);
}
}
///helper function don’t need to care
bool BFS(int S, int T){
queue<int> q({S});
fill(d.begin(),d.end(),N+1);
d[S] = 0;
while(!q.empty()){
int u = q.front(); q.pop();
if (u == T) break;
for (int k : g[u]){
Edge &e = E[k];
if (e.flow < e.cap && d[e.v] > d[e.u] + 1){
d[e.v] = d[e.u] + 1;
q.emplace(e.v);
}
}
}
return d[T] != N+1;
}
///helper function don’t need to care
long long DFS(int u, int T, long long flow = -1){
if (u == T || flow == 0) return flow;
for (int &i = pt[u]; i < g[u].size(); ++i){
Edge &e = E[g[u][i]];
Edge &oe = E[g[u][i]^1];
if (d[e.v] == d[e.u] + 1){
long long amt = e.cap-e.flow;
if (flow != -1 && amt > flow) amt = flow;
if (long long pushed = DFS(e.v,T,amt)){
e.flow += pushed;
oe.flow -= pushed;
return pushed;
}
}
}
return 0;
}
///find max flow from source to dest
long long MaxFlow(int S, int T){
long long total = 0;
while (BFS(S,T)){
fill(pt.begin(),pt.end(),0);
while (long long flow = DFS(S,T)) total += flow;
}
return total;
}
///This returns a list of edges used in the flow. If you want the edges with no flow, remove the e.flow != 0 condition
vector<Edge> retrieveFlow(){
vector<Edge> v;
for(auto &e : E ){
if(e.cap != 0 && e.flow != 0) v.push_back(e);
}
return v;
}
};
typedef pair<int,int> ii;
ii H[100005];
ii V[100005];
int main(){
//freopen("i.txt","r",stdin);
ios_base::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
for(int i = 1;i <= n;i++){
int x, y; cin >> x >> y;
if(H[x].first == 0) H[x].first = i;
else H[x].second = i;
if(V[y].first == 0) V[y].first = i;
else V[y].second = i;
}
vector<ii> edges;
for(int i = 0;i < 100005;i++){
if(H[i].first != 0 && H[i].second != 0) edges.push_back(ii(H[i].first, H[i].second));
if(V[i].first != 0 && V[i].second != 0) edges.push_back(ii(V[i].first, V[i].second));
}
int source = 0;
int sink = 2*n+1;
vector<int> perm;
for(int i = 1;i <= n;i++) perm.push_back(i);
for(int k = 0;k < 100;k++){
Dinic MF(2*n+2);
for(ii x : edges){
MF.addEdge(x.first, x.second + n, 1);
}
for(int i = 1;i <= n;i++){
MF.addEdge(i + n, sink, 1);
}
random_shuffle(perm.begin(),perm.end());
for(int i = 0;i < n/2;i++){
MF.addEdge(source, perm[i], 1);
}
if(MF.MaxFlow(source, sink) == n/2){
cout << "DA\n";
for(Edge e : MF.retrieveFlow()){
if(e.u != source && e.v != sink) cout << e.u << " " << e.v - n << "\n";
}
exit(0);
}
}
cout << "NE";
}
Compilation message
matching.cpp: In member function 'long long int Dinic::DFS(int, int, long long int)':
matching.cpp:46:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int &i = pt[u]; i < g[u].size(); ++i){
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
