【日常小测】最长路径

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf

解题报告

首先我们要熟悉竞赛图的两个结论:

  1. 任意一个竞赛图一定存在哈密尔顿路径
  2. 一个竞赛图存在哈密尔顿回路当且仅当这个竞赛图强连通

现在考虑把强连通分量缩成一个点,并把新点按照哈密尔顿路径排列
那么$1$号点可以到达的点数就是$1$号点所在的$SCC$的点数加上$1$号点可以到达的其他$SCC$点数和

设$f_i$为$i$个点带标号竞赛图的个数
设$g_i$为$i$个点带标号强连通竞赛图的个数
有$f_i = 2^{\frac{n(n-1)}{2}}$
又有$g_i = f_i – \sum\limits_{j = 1}^{i – 1}{{{i}\choose{j}} g_j f_{i – j}}$

于是我们枚举$1$号点所在$SCC$的点数$i$和$1$号点可到达的其他$SCC$的点数和$j$
$ans_{x} = \sum\limits_{i = 1}^{x}{{{n – 1}\choose{i – 1}} g_i {{n – i}\choose{x – i}} f_{x – i} f_{n – x}}$

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 2009;

int n, MOD, f[N], g[N], pw[N * N], C[N][N];

inline int read() {
	char c = getchar();
	int ret = 0, f = 1;
	while (c < '0' || c > '9') {
		f = c == '-'? -1: 1;
		c = getchar();
	}
	while ('0' <= c && c <= '9') {
		ret = ret * 10 + c - '0';
		c = getchar();
	}
	return ret * f;
}

int main() {
	freopen("path.in", "r", stdin);
	freopen("path.out", "w", stdout);
	n = read(); MOD = read();
	pw[0] = 1;
	for (int i = 1; i < n * n; i++) {
		pw[i] = (pw[i - 1] << 1) % MOD;
	}
	C[0][0] = 1;
	for (int i = 1; i <= n; ++i) {
		C[i][0] = 1;
		for (int j = 1; j <= n; j++) {
			C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
		}
	}
	f[0] = g[0] = 1;
	for (int i = 1; i <= n; i++) {
		f[i] = g[i] = pw[i * (i - 1) >> 1];
		for (int j = 1; j < i; j++) {
			g[i] = (g[i] - (LL)C[i][j] * g[j] % MOD * f[i - j]) % MOD;
		}
	}
	for (int x = 1; x <= n; x++) {
		int ans = 0;
		for (int i = 1; i <= x; i++) {
			ans = (ans + (LL)C[n - 1][i - 1] * g[i] % MOD * C[n - i][x - i] % MOD * f[x - i] % MOD * f[n - x]) % MOD;
		}
		printf("%d\n", ans > 0? ans: ans + MOD);
	}
	return 0;
}

【Codeforces 723E】One-Way Reform

题目传送门:http://codeforces.com/contest/723/problem/E
官方题解:http://codeforces.com/blog/entry/47502

出度与入度相等 => 欧拉回路
有度数为偶数的点 => 两两配对之后加一条边
此时所有点的度数都为偶数,每一个连通子图存在欧拉回路
于是可以用随便定向,只有用网络流来的得出可行解

现在唯一的问题就是证明度数为奇数的点一定是偶数对了:
一条边贡献两个度 => 总度数为偶数
若度数为奇数的点有奇数个 => 总度数为奇数
矛盾 => 度数为奇数的点不可能有奇数个

【BZOJ 2095】[Poi2010] Bridges

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2095

这个题目啊!瞄一眼就知道是二分吧?
接下来就是给你一些有向边&无向边,让你判断是否存在欧拉回路

对于有向边,没有悬念,直接记录对于出度入度的贡献
只与有向边嘛,不妨先随便定一个向,然后考虑使用网络流进行调整
具体细节可以参见:http://blog.csdn.net/wzq_qwq/article/details/48651379

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 2000+9;
const int M = 10000+9;
const int INF = 1e9;

struct Edge{int u,v,w1,w2;}edge[M];
int n,m,MX,MN=INF,in[N],out[N],cur[M];
int S,T,dis[N],flow[M],head[N],nxt[M],to[M],TT; 
queue<int> que;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void Add_Edge(int u, int v, int f) {
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
} 

inline bool BFS(){
	memset(dis,-1,sizeof(dis));
	dis[S] = 0; que.push(0);
	
	while (!que.empty()) {
		int w = que.front(); que.pop();
		for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]]) {
			dis[to[i]] = dis[w] + 1;
			que.push(to[i]);
		}
	}
	
	return ~dis[T];
}

int DFS(int w, int f) {
	if (w == T) {
		return f;
	} else {
		int ret = 0;
		for (int &i=cur[w],tmp;i && f;i=nxt[i]) { 
			if (dis[to[i]] == dis[w] + 1) {
				tmp = DFS(to[i], min(f, flow[i]));
				ret += tmp; f -= tmp;
				flow[i] -= tmp; flow[i^1] += tmp;
			}
		}
		return ret;
	}
}

inline int Dinic(){
	int ret = 0;
	while (BFS()) {
		memcpy(cur,head,sizeof(head));
		ret += DFS(S,INF);
	}
	return ret;
}

inline bool judge(int lim){
	memset(in,0,sizeof(in));
	memset(out,0,sizeof(out));
	memset(head,0,sizeof(head));
	S = 0; T = N - 1; TT = 1;
	int tot = 0;
	
	for (int i=1;i<=m;i++) {
		if (lim < edge[i].w1) {
			continue;
		} else if (lim < edge[i].w2) {
			in[edge[i].v]++;
			out[edge[i].u]++;
		} else {
			in[edge[i].v]++;
			out[edge[i].u]++;
			Add_Edge(edge[i].u, edge[i].v, 2);
		}
	}
	
	for (int i=1;i<=n;i++) {
		if (abs(in[i]-out[i]) & 1) {
			return false;
		} else if (in[i] < out[i]) {
			Add_Edge(S,i,out[i]-in[i]);	
			tot += out[i] - in[i];
		} else if (in[i] > out[i]) {
			Add_Edge(i,T,in[i]-out[i]);
		}
	}
	
	return Dinic() == tot;
}

int main(){
	n = read(); m = read();
	for (int i=1;i<=m;i++) {
		edge[i].u = read();
		edge[i].v = read();
		edge[i].w1 = read();	
		edge[i].w2 = read();
		if (edge[i].w1 > edge[i].w2) {
			swap(edge[i].w1, edge[i].w2);
			swap(edge[i].u, edge[i].v);
		}
		MX = max(MX, edge[i].w2);
		MN = min(MN, edge[i].w1);
	}
	
	int l = MN, r = MX, mid, ret = -1;
	while (l <= r) {
		mid = l + r >> 1;
		if (judge(mid)) ret = mid, r = mid - 1;
		else l = mid + 1;
	}
	if (~ret) printf("%d\n",ret);
	else puts("NIE");
	return 0;
}