题目传送门:http://uoj.ac/problem/78
离线版题目:http://paste.ubuntu.com/19130171/
今天来搞一搞图论,先来一发二分图。
Dinic此题的时间还是不错的,能踩Dinic的,都只有二分图专门的算法
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN = 5000000+9; const int INF = 10000000; int n1,n2,m,s,t,vout; int T=1,to[MAXN],nxt[MAXN],head[MAXN]; int dis[MAXN],que[MAXN],fro,bak; int cap[MAXN],flow[MAXN],cur[MAXN]; inline int read(){ char c=getchar(); int buf=0,f=1; while (c<'0'||c>'9'){if(c=='-')f=-1;;c=getchar();} while (c<='9'&&c>='0'){buf=buf*10+c-'0';c=getchar();} return buf*f; } inline void AddEdge(int a, int b, int CAP){ to[++T] = b; nxt[T] = head[a]; head[a] = T; cap[T] = CAP; to[++T] = a; nxt[T] = head[b]; head[b] = T; cap[T] = 0; } inline bool BFS(){ memset(dis,-1,sizeof(dis)); que[fro=bak=1] = s; dis[s] = 0; while (bak <= fro) { int w = que[bak++]; for (int i=head[w];i;i=nxt[i]) if (flow[i] < cap[i] && dis[to[i]] == -1) dis[to[i]] = dis[w] + 1, que[++fro] = to[i]; } return dis[t] != -1; } int MaxFlow(int w, int f){ if (w == t) return f; else { int ret = 0; for (int &i=cur[w];i;i=nxt[i]){ if (flow[i] < cap[i] && dis[to[i]] == dis[w] + 1){ int tmp = MaxFlow(to[i], min(f, cap[i]-flow[i])); flow[i] += tmp; flow[i^1] -= tmp; ret += tmp; if (ret == f) return ret; } } return ret; } } inline void Dinic(){ while (BFS()){ for (int i=0;i<=t;i++) cur[i] = head[i]; vout += MaxFlow(s, INF); } } int main(){ n1=read(); n2=read(); m=read(); s = 0; t = n1 + n2 + 1; for (int i=1,a,b;i<=m;i++) a = read(), b = read(), AddEdge(a,n1+b,1); for (int i=1;i<=n1;i++) AddEdge(s,i,1); for (int i=n1+1;i<=n1+n2;i++) AddEdge(i,t,1); Dinic(); printf("%d\n",vout); for (int w=1;w<=n1;w++){ vout = 0; for (int i=head[w];i;i=nxt[i]) if (flow[i] && to[i] > n1) { vout = to[i]-n1; break; } printf("%d\n",vout); } return 0; }