Category: 图论

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

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

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

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1001
数据生成器：http://paste.ubuntu.com/18772741/

最大流板题，输入搞反了，调了3hQAQ

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
 
const int N = 1000000+9;
const int INF = 1000000000;
 
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;
}
 
int n,m,head[N],to[N*6],nxt[N*6],cap[N*6],T,flow[N*6];
int vout,cur[N],que[N],dis[N],fro,bak,tot,s,t;
 
#define id(x,y) (((y)-1)*n+(x))
 
inline void AddEdge(int u, int v, int MX){
    to[++T] = v; nxt[T] = head[u]; head[u] = T; cap[T] = MX;
    to[++T] = u; nxt[T] = head[v]; head[v] = T; cap[T] = MX;
}
 
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];
        }
    }
    if (dis[t] == -1) return false;
    else return true;
}
 
int MaxFlow(int w, int f){
    if (w==t) {vout += f;return f;}
    else {
        int ret = 0;
        for (int &i=cur[w],tmp;i;i=nxt[i]){
            if (flow[i] < cap[i] && dis[to[i]]==dis[w]+1){
                tmp = MaxFlow(to[i], min(f, cap[i]-flow[i]));
                f -= tmp; ret += tmp;
                flow[i] += tmp; flow[i^1] -= tmp;
                if (!f) return ret;
            }
        }
        return ret;
    }
}
 
inline void Dinic(){
    tot = id(n,m);
    while (BFS()){
        for (int i=1;i<=tot;i++)
            cur[i] = head[i];
        MaxFlow(s,INF);
    }   
}
 
int main(){
    m = read(); n = read(); s = id(1,1); t = id(n,m); T = 1;
    for (int j=1;j<=m;j++) for (int i=1;i<n;i++) AddEdge(id(i,j),id(i+1,j), read());
    for (int j=1;j<m;j++) for (int i=1;i<=n;i++) AddEdge(id(i,j),id(i,j+1), read());
    for (int j=1;j<m;j++) for (int i=1;i<n;i++) AddEdge(id(i,j),id(i+1,j+1),read());
    if (s != t) Dinic();
    printf("%d\n",vout);
    return 0;
}

最近几天，重新来看网络流的相关题目，发现之前看的基本上都忘了 QAQ
看了一个上午，有以下收获
1.最大流的正确性依赖于每一条s-t流对应了一种实际方案
2.网络流也可以作为二分的可行解判定方式
3.网络流只能在0/1之中做选择，对于1/2、2/3之类的，可以考虑降到0/1之后算贡献
4.对于割边，可以在残余网络中DFS搞一搞，一端可到源点，一端可到汇点即为割边

另外，提供一点网络流24题的相关资源：
1.完整题解：http://www.snowyjone.me/2015/07/lp-and-flow-a/
2.精选题解：https://blog.sengxian.com/solutions/networkflow-24-all
3.大神题解：https://www.byvoid.com/blog/lpf24-solution
4.OJ传送门：http://cojs.tk/cogs/page/page.php?aid=3

题目传送门：http://pan.baidu.com/s/1eRRG6Wy
离线版题目：http://paste.ubuntu.com/18687179/
数据传送门：http://pan.baidu.com/s/1qYtM8f6
数据生成器：http://paste.ubuntu.com/18687249/

唉，以前在CF上，看过这道题，拿到后，一眼就记得跟线段树有关，然而还是没有做出来QAQ
说一说怎么做：
如果边权很小，那么我们直接跑最短路就好，如果边权再大一点，那我们就写高精度
然而这题有2^100000，这个大概有10000那么多位（DEC），高精度会T，而且空间也开不下
所以只能搞神奇的技巧。
我们那函数式线段树来模拟二进制数组。那么单次修改就是log（n）的时间和空间复杂度
那么，比较大小怎么搞？搞一搞Hash，然后找到第一位不同的地方比较大小，仍然是log（n）
那么怎么进位？单点赋一，区间赋零即可，也为log（n）
然后就是码代码的事情了，我代码只写了一个小时，然而调试了3小时QAQ

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 200000+9;
const int MOD = 1000000000+7;
const int HASH = 9999971;
const int SEED = 137;
const int INF = 100000000;

int n,m,T,to[MAXN],head[MAXN],nxt[MAXN],cost[MAXN];
int s,t,done[MAXN],tpw[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;
}

namespace Chair_Tree{
	#define CT Chair_Tree
	#define N 10000000
	#define MX 200000
	int root[MAXN],hash[N],val[N],ch[N][2],MN[N];
	int ans_tmp,cnt;
	
	inline bool cmp(int w1, int w2){
		int l=1,r=MX,mid;
		while (l < r){
			mid = (l+r+1)/2;
			if (hash[ch[w1][1]] != hash[ch[w2][1]] || val[ch[w1][1]] != val[ch[w2][1]]) 
			w1 = ch[w1][1], w2 = ch[w2][1], l = mid;
			else w1 = ch[w1][0], w2 = ch[w2][0], r = mid-1; 
		}	
		return val[w1] > val[w2];
	}
	
	void find(int w, int l, int r, int pos){
		if (!w) ans_tmp = min(ans_tmp, l);
		else if (l >= pos) ans_tmp = min(ans_tmp, MN[w]);
		else if (r >= pos && l < r) {
			int mid = (l+r+1) / 2;
			if (pos < mid) find(ch[w][0], l, mid-1, pos);
			find(ch[w][1], mid, r, pos);
		}
	}inline int find(int w, int pos){ans_tmp = INF;find(w, 1, MX, pos);return ans_tmp;}	
	
	inline void maintain(int w, int l, int r){
		int len = (l+r+1)/2-l; MN[w] = INF;
		hash[w] = (LL)((LL)hash[ch[w][0]]+(LL)SEED*hash[ch[w][1]])*SEED % HASH;
		val[w] = (LL)((LL)val[ch[w][0]] + (LL)val[ch[w][1]]*tpw[len]) % MOD;
		if (ch[w][0]) MN[w] = min(MN[w], MN[ch[w][0]]);
		else MN[w] = min(MN[w], l);
		if (ch[w][1]) MN[w] = min(MN[w], MN[ch[w][1]]);
		else MN[w] = min(MN[w], (l+1+r)/2);
		if (l == r && !val[w]) MN[w] = min(MN[w], l);
	}
	
	void modify(int pre, int &w, int l, int r, int p){
		w = ++cnt; ch[w][0] = ch[pre][0]; ch[w][1] = ch[pre][1];
		if (l == r) hash[w] = 1, val[w] = 1, MN[w] = INF;
		else {
			int mid = (l+r+1) / 2;
			if (p < mid) modify(ch[pre][0], ch[w][0], l, mid-1, p);
			else modify(ch[pre][1], ch[w][1], mid, r, p);
			maintain(w,l,r);
		}
	}
	
	void clear(int pre, int &w, int l, int r, int L, int R){
		int mid = (l+r+1) / 2;
		if (L <= l && r <= R) w = 0;
		else {
			w = ++cnt; ch[w][0] = ch[pre][0]; ch[w][1] = ch[pre][1];
			if (L < mid) clear(ch[pre][0], ch[w][0], l, mid-1, L, R);
			if (R >= mid) clear(ch[pre][1], ch[w][1], mid, r, L, R);
			maintain(w,l,r);
		}  
	}
	
	inline int Add(int rt, int pos){
		int p1 = max(find(rt, pos),pos), ret;
		modify(rt, ret, 1, MX, p1);
		if (p1 > pos) clear(ret, ret, 1, MX, pos ,p1-1);
		return ret;
	}
	
	inline void output(int rt){
		printf("%d\n",val[rt]%MOD);
	}
	
	inline void print_path(){
		int w = t; cout<<t<<endl;
		while (w != s){
			for (int i=head[w];i;i=nxt[i]){
				int tmp = Add(root[to[i]], cost[i]);
				if (cmp(tmp,root[w])^cmp(root[w],tmp)==0) 
					w = to[i], cout<<w<<' '<<val[root[w]]<<endl;
			}
		}
		cout<<s;
	}
	
	void build(int &w, int l, int r){
		w = ++cnt; MN[w] = INF;
		if (l == r) hash[w] = val[w] = 1;
		else {
			int mid = (l+r+1)/2;
			build(ch[w][0], l, mid-1);
			build(ch[w][1], mid, r);
			maintain(w,l,r);
		}
	}inline int build_Tree(){int ret; build(ret,1,MX); return ret;}
};

struct DATA{
	int p,rt; DATA(){}
	DATA(int P, int RT):p(P),rt(RT){}
	bool operator < (const DATA &B) const {
		return CT::cmp(rt, B.rt);
	}
};
priority_queue<DATA> Q;

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

inline void Dijkstra(){
	int tmp = CT::build_Tree();
	for (int i=1;i<=n;i++) CT::root[i] = tmp;
	CT::root[s] = 0;
	Q.push(DATA(s,CT::root[s]));
	
	while (!Q.empty()){
		DATA w = Q.top(); Q.pop();
		if (done[w.p]) continue;
		else if (w.p == t) {
			CT::output(w.rt);return;		
		} else {
			done[w.p] = 1;
			for (int i=head[w.p];i;i=nxt[i]){
				if (done[to[i]]) continue;
				else {
					tmp = CT::Add(w.rt,cost[i]);
					if (CT::cmp(CT::root[to[i]], tmp))
						CT::root[to[i]] = tmp, 
						Q.push(DATA(to[i], tmp));		
				}
			}	
		}
	}
	printf("-1\n");
}

int main(){
	freopen("shortest.in","r",stdin);
	freopen("shortest.out","w",stdout);
	n = read(); m = read();
	for (int i=1,a,b,c;i<=m;i++)
		a=read(), b=read(), c=read(),
		AddEdge(a, b, c+1);
	s = read(); t = read(); tpw[0] = 1; 
	for(int i=1;i<=150000;i++)
		tpw[i] = (LL)tpw[i-1]*2%MOD;
 	
	Dijkstra();
	
	return 0;
}

写这篇文章主要是因为最近考了一道弦图染色方案数的题目
网上很容易查到弦图的最少染色数的相关资料但却找不到染色方案数的资料
于是自己和学长搞了一份出来，证明不是很严谨，但正确性应该没有问题 o(*￣▽￣*)ブ
Chordal_Graph