【UOJ 78】二分图最大匹配

题目传送门: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;
} 

【COGS 396】[网络流24题] 魔术球问题

题目传送门:http://cogs.top/cogs/problem/problem.php?pid=396
离线版题目:http://paste.ubuntu.com/18780019/

贪心即可。因为枚举一下,1600以内,加上比自己小的数为完全平方数没有多解,所以只要能加,加上去就好
当然, 正解是最少路径覆盖+二分,然而为什么要闲得蛋疼写Dinic ╮(╯-╰)╭
另外,COGS的浮点运算取整是辣鸡QAQ,害的我wa了好几发……

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;

const int MAXN = 10000;
const int MX = 1600;

int n,tot,arr[MAXN],vout;

inline bool judge(int num){
	for (int i=1;i<=tot;i++){
		int tmp = sqrt(arr[i]+num);
		if (tmp*tmp == arr[i]+num){
			arr[i] = num; 
			return true;
		}
	}
	if (tot < n) {arr[++tot] = num; return true;}
	return false;
}

int main(){  
	freopen("balla.in","r",stdin);
	freopen("balla.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=MX;i++)
		if (judge(i)) vout=i;
		else {printf("%d\n",i-1);break;}
	return 0;
} 

【COGS 14】[网络流24题] 搭配飞行员

题目传送门:http://cogs.top/cogs/problem/problem.php?pid=14
离线版题目:http://paste.ubuntu.com/18772859/

二分图匹配板题,Dinic跑一跑就ok啦!

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

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;
}

const int MAXN = 10000+9;
const int INF = 1000000000;

int n,m,a,b,T,head[MAXN],to[MAXN],nxt[MAXN],cap[MAXN],vout;
int s,t,cur[MAXN],que[MAXN],fro,bak,dis[MAXN],flow[MAXN];

inline void AddEdge(int a, int b){
	to[++T] = b; nxt[T] = head[a]; head[a] = T; cap[T] = 1;
	to[++T] = a; nxt[T] = head[b]; head[b] = T;  
}

inline bool BFS(){
	memset(dis,-1,sizeof(dis));
	dis[s] = 0; que[fro=bak=1]=s;
	
	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];
	}
	
	if (dis[t] != -1) return true;
	else return false;
}

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; f-=tmp;
				if (!f) return ret;
			}
		}
		return ret;
	}
}

inline void Dinic(){
	while (BFS()){
		for (int i=0;i<=n*2+1;i++)
			cur[i] = head[i];
		vout += MaxFlow(s,INF);
	}
}

int main(){
	freopen("flyer.in","r",stdin);
	freopen("flyer.out","w",stdout);
	n = read(); m = read();
	s = 0; t = 2*n+1; T = 1;
	while (~scanf("%d%d",&a,&b)) AddEdge(a*2,b*2-1);
	for (int i=1;i<=m;i++) AddEdge(s,i*2-1);
	for (int i=m+1;i<=n;i++) AddEdge(i*2,t);
	for (int i=1;i<=n;i++) AddEdge(i*2-1,i*2);
	Dinic();
	printf("%d\n",vout);
	return 0;
}