Submission #223446

#	Time	Username	Problem	Language	Result	Execution time	Memory
223446		oolimry	Matching (COCI20_matching)	C++14	0 / 110	6 ms	384 KiB

matching

#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 (stderr)

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){
                              ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 40
• Subtask 5: 0 / 52