FLOW1 - Giao lưu

Tác giả: skyvn97

Ngôn ngữ: C++

#include<bits/stdc++.h>
#define MAX   257
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define fi   first
#define se   second
using namespace std;
const int INF=(int)1e9+7;
typedef pair<int,int> ii;
class DinicFlow {
	public:
	vector<int> dist,head,q,work;
	vector<int> capa,flow,next,point;
	int n,m;
	DinicFlow() {
		n=0;m=0;		
	}
	DinicFlow(int n,int _m) {
		this->n=n;
		this->m=0;
		dist=vector<int>(n+7);
		head=vector<int>(n+7,-1);
		q=vector<int>(n+7);		
		work=vector<int>(n+7);
		int m=2*_m;
		capa=vector<int>(m+7);
		flow=vector<int>(m+7,0);
		next=vector<int>(m+7);
		point=vector<int>(m+7);		
	}
	int addedge(int u,int v,int c1,int c2) {		
		assert(c1==1 && c2==0);
		point[m]=v;capa[m]=c1;flow[m]=0;next[m]=head[u];head[u]=m;m++;
		point[m]=u;capa[m]=c2;flow[m]=0;next[m]=head[v];head[v]=m;m++;
		return (m-2);
	}
	bool bfs(int s,int t) {
		FORE(it,dist) *it=-1;
		int sz=1;
		q[0]=s;dist[s]=0;
		REP(x,sz) {
			int u=q[x];
			for (int i=head[u];i>=0;i=next[i])
				if (dist[point[i]]<0 && flow[i]<capa[i]) {
					dist[point[i]]=dist[u]+1;
					q[sz]=point[i];
					sz++;
				}
		}
		return (dist[t]>=0);
	}
	int dfs(int s,int t,int f) {
		if (s==t) return (f);
		for (int &i=work[s];i>=0;i=next[i])
			if (dist[point[i]]==dist[s]+1 && flow[i]<capa[i]) {
				int d=dfs(point[i],t,min(f,capa[i]-flow[i]));
				if (d>0) {
					flow[i]+=d;
					flow[i^1]-=d;
					return (d);
				}
			}
		return (0);
	}
	int maxflow(int s,int t) {
		int ret=0;
		while (bfs(s,t)) {
			FOR(i,1,n) work[i]=head[i];
			while (true) {
				int d=dfs(s,t,INF);
				if (d<=0) break;
				ret+=d;
			}
		}
		return (ret);
	}
};
DinicFlow g;
int m,n;
vector<ii> fth[MAX],fsp[MAX];
ii res[MAX];
void init(void) {	
	cin >> n >> m;	
	int ne=2*n+m;
	string zz;
	getline(cin,zz);
	FOR(i,1,n) {
		string tmp;
		getline(cin,tmp);
		stringstream ss;
		ss << tmp;
		int t;
		while (ss >> t) {
			fth[i].push_back(ii(t,0));
			ne++;
		}
	}
	FOR(i,1,n) {
		string tmp;
		getline(cin,tmp);
		stringstream ss;
		ss << tmp;
		int t;
		while (ss >> t) {
			fsp[i].push_back(ii(t,0));
			ne++;
		}
	}	
	g=DinicFlow(2*(n+m+1),ne);		
	FOR(i,1,n) {
		FORE(it,fth[i]) it->se=g.addedge(i,n+it->fi,1,0);
		FORE(it,fsp[i]) it->se=g.addedge(n+m+it->fi,i+n+2*m,1,0);	
		g.addedge(2*(n+m)+1,i,1,0);
		g.addedge(n+2*m+i,2*(n+m+1),1,0);
	}
	FOR(i,1,m) g.addedge(n+i,n+m+i,1,0);	
}
void process(void) {
	assert(g.maxflow(2*(n+m)+1,2*(n+m+1))==n);
	FOR(i,1,m) res[i]=ii(0,0);
	FOR(i,1,n) {
		FORE(it,fth[i]) if (g.flow[it->se]>0) res[it->fi].fi=i;
		FORE(it,fsp[i]) if (g.flow[it->se]>0) res[it->fi].se=i;
	}
	FOR(i,1,m) printf("%d %d\n",res[i].fi,res[i].se);
}
int main(void) {
#ifndef ONLINE_JUDGE
	freopen("tmp.txt","r",stdin);
#endif	
	init();
	process();
}

Download