【日常小测】最长路径

相关链接

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

【算法笔记】Kosaraju算法

前言

今天考了一套$Claris$的题
$T1$就是$Claris$用$bitset$配合这个算法把求$SCC$优化到了$\frac{n^2}{32}$
吓得我赶紧来学了学

算法概述

$step \ 1.$ DFS一遍,记录下后序遍历的顺序
$step \ 2.$ 沿后续遍历的逆序、沿反向边再DFS一遍,每一个连通块即为一个SCC

算法解释

设原图为图$G$,将$SCC$缩点后的新图为$G’$
第一遍$DFS$保证了在若某个强连通分量$A$在$G’$中是另一个强连通分量$B$的祖先
那么在后续遍历的逆序中至少存在一个点$A$中的点在$B$中所有点的前面

这样在第二次$DFS$的时候,因为是逆序,所以只能往$G’$中的祖先走
又因为祖先的$SCC$已经标记过了,所以刚好把当前$SCC$搞完,不会有多

这算法太妙了

代码实现

int scc_cnt, vis[N];
vector<int> scc_cnt[N], que;
void DFS0(int w) {
	vis[w] = 0;
	for (int i = head[w]; i; i = nxt[i]) {
		if (!vis[to[i]]) {
			DFS0(to[i]);
		}
	}
	que[++tot] = w;
}
void DFS1(int w) {
	scc[scc_cnt].push_back(w);
	vis[w] = 1;
	for (int i = rev_head[w]; i; i = nxt[i]) {
		if (!vis[to[i]]) {
			DFS1(to[i]);
		}
	}
} 
void solve() {
	que.clear();
	memset(vis, 0, sizeof(vis));
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			DFS0(i);
		}
	}
	scc_cnt = 0;
	memset(vis, 0, sizeof(vis));
	for (int i = (int)que.size() - 1; ~i; i--) {
		if (!vis[que[i]]) {
			scc_cnt++;
			DFS1(que[i]);
		}
	}
}

使用$bitset$优化

这货复杂度是$O(m)$的
不难发现算法瓶颈在查找与某个点相邻的所有点中还没有被访问过的点
这个可以用$bitset$压位并配合__builtin开头的系列函数优化到$O(\frac{n^2}{32})$
例题的话,可以参考:友好城市

【日常小测】友好城市

相关链接

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

解题报告

这题的前置知识是把求$SCC$优化到$O(\frac{n^2}{32})$
具体来说,就是使用$bitset$配合$Kosaraju$算法

有了这个技能以后,我们配合$ST$表来实现提取一个区间的边的操作
这样的话,总的时间复杂度是:$O(\frac{(\sqrt{m} \log m + q) n^2}{32}+q \sqrt{m})$

然后我懒,没有用$ST$表,用的莫队,时间复杂度是$O(\frac{(m + q) n^2}{32}+q \sqrt{m})$
调一调块大小,勉勉强强卡过去了

Code

#include<bits/stdc++.h>
#define LL long long
#define UI unsigned int 
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 159;
const int M = 300009;
const int QQ = 50009;
const int BlockSize = 1200;
const UI ALL = (1ll << 32) - 1;

int n, m, q, U[M], V[M], ans[QQ]; 
struct Query{
	int l, r, blk, id;
	inline bool operator < (const Query &Q) const {
		return blk < Q.blk || (blk == Q.blk && r < Q.r);
	}
}qy[QQ];
struct Bitset{
	UI v[5];
	inline void flip(int x) {
		v[x >> 5] ^= 1 << (x & 31);
	}
	inline void set(int x) {
		v[x >> 5] |= 1 << (x & 31);
	}
	inline void reset() {
		memset(v, 0, sizeof(v));
	}
	inline bool operator [](int x) {
		return v[x >> 5] & (1 << (x & 31));
	}
}g[N], rg[N], PreG[M / BlockSize + 9][N], PreRG[M / BlockSize + 9][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;
}

inline void AddEdge(int u, int v, Bitset *a1, Bitset *a2) {
 	a1[u].set(v);
 	a2[v].set(u);
}

class Kosaraju{
	vector<int> que;
	Bitset vis;
public:
	inline int solve() {
		vis.reset();
		que.clear();
		for (int i = 1; i <= n; ++i) {
			if (!vis[i]) {
				dfs0(i);
			}
		}
		vis.reset();
		int ret = 0;
		for (int j = n - 1; ~j; j--) {
			int i = que[j];
			if (!vis[i]) {
				int cnt = dfs1(i);
				ret += cnt * (cnt - 1) / 2;
			}
		}
		return ret;
	}
private:
	inline void dfs0(int w) {
		vis.flip(w);
		for (int i = 0; i < 5; i++) {
			for (UI j = g[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
				int t = (__builtin_ffs(j) - 1) | (i << 5);
				if (!vis[t]) {
					dfs0(t);
				}
			}
		}
		que.push_back(w);
	}
	inline int dfs1(int w) {
		vis.flip(w);
		int ret = 1;
		for (int i = 0; i < 5; i++) {
			for (UI j = rg[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
				int t = (__builtin_ffs(j) - 1) | (i << 5);
				if (!vis[t]) {
					ret += dfs1(t);
				}
			}
		}
		return ret;
	}
}scc;

int main() {
	freopen("friend.in", "r", stdin);
	freopen("friend.out", "w", stdout);
	n = read(); m = read(); q = read();
	for (int i = 1; i <= m; i++) {
		U[i] = read();
		V[i] = read();
		AddEdge(U[i], V[i], PreG[i / BlockSize], PreRG[i / BlockSize]);
	}
	for (int i = 1; i <= q; i++) {
		qy[i].l = read(); 
		qy[i].r = read();
		qy[i].blk = qy[i].l / BlockSize;
		qy[i].id = i;
	}
	sort(qy + 1, qy + 1 + q);
	Bitset CurG[N], CurRG[N];
	for (int i = 1, L = 1, R = 0; i <= q; i++) {
		if (qy[i].blk != qy[i - 1].blk || i == 1) {
			L = qy[i].blk + 1;
			R = L - 1;	
			for (int j = 1; j <= n; j++) {
				CurG[j].reset();
				CurRG[j].reset();
			}
		}
		if (qy[i].r / BlockSize - 1 > R) {
			for (int j = R + 1, lim = qy[i].r / BlockSize - 1; j <= lim; j++) {
				for (int k = 1; k <= n; k++) {
					for (int h = 0; h < 5; h++) {
						CurG[k].v[h] ^= PreG[j][k].v[h];
						CurRG[k].v[h] ^= PreRG[j][k].v[h];
					}
				}
			}
			R = qy[i].r / BlockSize - 1;
		}
		if (L <= R) {
			for (int i = 1; i <= n; i++) {
				g[i] = CurG[i];
				rg[i] = CurRG[i];
			}
			for (int l = qy[i].l; l < L * BlockSize; l++) {
				AddEdge(U[l], V[l], g, rg);
			}
			for (int r = (R + 1) * BlockSize; r <= qy[i].r; r++) {
				AddEdge(U[r], V[r], g, rg);
			}
			ans[qy[i].id] = scc.solve();
		} else {
			for (int i = 1; i <= n; i++) {
				g[i].reset();
				rg[i].reset();
			}
			for (int j = qy[i].l; j <= qy[i].r; ++j) {
				AddEdge(U[j], V[j], g, rg);
			}
			ans[qy[i].id] = scc.solve();
		}
	}
	for (int i = 1; i <= q; i++) {
		printf("%d\n", ans[i]);
	}
	return 0;
}

【BZOJ 4886】[Lydsy2017年5月月赛] 叠塔游戏

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4886
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/05/ludsy_may_contest_solution.pdf

解题报告

我们把权值看做点,矩形看作边
不难发现一个大小为$n$连通块如果是树,那么最多选$n-1$个点
否则可以选完$n$个点

所以用并查集维护一下连通性之后
直接贪心即可

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
  
const int N = 500009;
  
int n,tot,u[N],v[N],fa[N],val[N],cir[N],sz[N]; 
LL ans;
  
inline int read() {
    char c=getchar(); int f=1,ret=0;
    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;
}
  
int find(int x) {
    return x == fa[x]? x: fa[x] = find(fa[x]);
}
  
int main() {
    n = read();
    for (int i=1;i<=n;i++) {
        u[i] = val[++tot] = read(); 
        v[i] = val[++tot] = read();
        ans += u[i];
        ans += v[i];
    }
    sort(val+1, val+1+tot);
    tot = unique(val+1, val+1+tot) - val - 1;
    for (int i=1;i<=tot;i++) {
        fa[i] = i;
        sz[i] = 1;
    }
    for (int i=1;i<=n;i++) {
        int x = lower_bound(val+1, val+1+tot, u[i]) - val;
        int y = lower_bound(val+1, val+1+tot, v[i]) - val;
        if (find(x) != find(y)) {
            sz[fa[y]] += sz[fa[x]];
            if (cir[fa[x]]) {
                cir[fa[y]] = 1;
            }
            fa[fa[x]] = fa[y];
        } else {
            cir[fa[x]] = 1;
        }
    } 
    for (int i=1;i<=tot;i++) {
        if (find(i) == i) {
            sz[i] -= (cir[i] ^ 1);
        }
    }
    for (int i=1,w=1;i<=n;i++,w++) {
        while (sz[find(w)] == 0) ++w;
        ans -= val[w]; 
        sz[fa[w]]--;
    }
    printf("%lld\n",ans);
    return 0;
}

【BZOJ 3033】太鼓达人

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3033
神犇题解:http://blog.csdn.net/clover_hxy/article/details/56003661

解题报告

这个东西,看一看样例,感觉答案是$2^k$,然后写一发无脑贪心就过了

不过这题的证明非常妙妙啊:

考虑将每一个$0 \sim 2^{k+1}-1$的数看成一个点,标号为这个数
把在这个数末尾或者开头加$0/1$看作边
那么每个点度数恰好为$4$,并且整个图显然连通
那么这图显然存在欧拉回路,那么就能够一笔画

于是在这个图上贪心走就可以了

Code

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

const int N = 3000;

int n,k,arr[N];
set<int> S;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	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 int get(int p) {
	int ret = 0;
	for (int i=0;i<k;i++) ret += (1 << i) * arr[p + i];
	return ret; 
}

int main() {
	k = read(); n = 1 << k;
	for (int i=1;i<=k;i++) arr[i] = 0; S.insert(0);
	for (int i=n;i>n-k;i--) arr[i] = 1, S.insert(get(i));
	for (int i=2;i<=n-k;i++) {
		if (S.count(get(i))) arr[i+k-1] = 1;
		S.insert(get(i));
	}
	printf("%d ",n);
	for (int i=1;i<=n;i++) printf("%d",arr[i]);
	return 0;
}

【日常小测】Mortal Kombat

题目大意

给定$n(n \le 300)$个外星人,给定$m(m \le 1500)$个地球人,再给定任意地球人与外星人的关系
关系由一个$nm$的0/1矩阵给出,表示第$i$个外星人是否能与第$j$个地球人配对
要求每个外星人至少与一个地球人配对,地球人只能与至多一个外星人匹配
问由哪些关系一定不可能出现在合法的匹配方案中

解题报告

这是一道基础图论题

我们可以先来考虑一个简单的版本:地球人个数与外星人一样
那么我们可以先用二分图匹配跑一个完备匹配出来
此时在匹配中的边一定可以出现在合法的匹配方案中

只考虑不在当前匹配中的边,那么一定是走一条像增广路一样的东西
就是一条匹配边,一条非匹配边交叉着走。最后走一个偶环绕回来
于是我们对于从左边连到右边的边,只保留非匹配边
对于从右到左的边,我们只保留匹配边。这样就可以保证是偶环了
至于能不能走回来,我们发现这就是一个有向图的强连通分量
于是我们再跑一个Tarjan,判断一下就可以了

现在考虑地球人与外星人不等的情况
我们可以把外星人补到与地球人一样多啊!
就是加一些可以与所有地球人匹配的外星人就可以了
当然不加点,大力讨论一波也是可以的

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
  
const int N = 3009;
const int M = N * N << 1;
const int INF = 1e9;
  
int head[N],nxt[M],to[M],flow[M],low[N],dfs[N];
int n,m,S,T,E=1,mth[N],id[N][N],num[N],ins[N]; char pat[N]; 
stack<int> stk;
  
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 int AddEdge(int u, int v, int f=0) {
    if (f) {
        to[++E] = v; nxt[E] = head[u]; head[u] = E;
        to[++E] = u, nxt[E] = head[v], head[v] = E;
        flow[E - 1] = f; return E - 1;
    } else to[++E] = v, nxt[E] = head[u], head[u] = E;
}
  
class Network_Flow{
    int dis[N],cur[N]; queue<int> que;
    public:
        inline int MaxFlow() {
            int ret = 0;
            while (BFS()) {
                memcpy(cur,head,sizeof(cur));
                ret += DFS(S, INF);
            } return ret;
        }
    private:
        int DFS(int w, int f) {
            if (w == T) return f; int ret = 0;
            for (int &i=cur[w],tmp;i;i=nxt[i]) {
                if (flow[i] && dis[to[i]] == dis[w] + 1) {
                    tmp = DFS(to[i], min(f, flow[i]));
                    flow[i] -= tmp; flow[i^1] += tmp;
                    f -= tmp; ret += tmp;
                    if (!f) return ret;
                }
            } return ret;
        }
        inline bool BFS() {
            memset(dis,60,sizeof(dis));
            dis[S] = 0; que.push(S);
            while (!que.empty()) {
                int w = que.front(); que.pop();
                for (int i=head[w];i;i=nxt[i]) {
                    if (flow[i] && dis[to[i]] > INF) {
                        dis[to[i]] = dis[w] + 1; 
                        que.push(to[i]);
                    }
                }
            } return dis[T] < INF;
        }
}Dinic;
 
void Tarjan(int w) { 
    static int dfs_cnt = 0, scc_cnt = 0; 
    dfs[w] = low[w] = ++dfs_cnt; stk.push(w); ins[w] = 1;
    for (int i=head[w];i;i=nxt[i]) {
        if (!dfs[to[i]]) Tarjan(to[i]), low[w] = min(low[w], low[to[i]]);
        else if (ins[to[i]]) low[w] = min(low[w], dfs[to[i]]);  
    }
    if (low[w] == dfs[w]) {
        for (scc_cnt++;!stk.empty();stk.pop()) {
            num[stk.top()] = scc_cnt; ins[stk.top()] = 0;
            if (stk.top() == w) {stk.pop(); break;}
        }
    }
}
 
int main() {
    n = read(); m = read(); S = 0; T = N - 1;
    memset(id, -1, sizeof(id));
    for (int i=1;i<=n;i++) {
        scanf("%s",pat+1);
        for (int j=1;j<=m;j++) {
            if (pat[j] == '1') {
                id[i][j] = AddEdge(i, m + j, 1);
            }   
        }
    } 
    for (int i=1;i<=n;i++) AddEdge(S, i, 1);
    for (int i=1;i<=m;i++) AddEdge(m + i, T, 1);
    if (Dinic.MaxFlow() != n) {
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=m;j++) putchar('1');
            puts("");
        }
    } else {
        E = 1; memset(head,0,sizeof(head));
        for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) 
            if (~id[i][j] && !flow[id[i][j]]) {mth[j] = i; break;}
        for (int i=n+1,j=1;i<=m;i++,j++) {while(mth[j])j++;mth[j]=i;}
        for (int i=1;i<=m;i++) for (int j=1;j<=m;j++) if (~id[i][j] || i > n) {
            if (mth[j] == i) AddEdge(m+j, i); else AddEdge(i, m+j);}
        for (int i=1;i<=m*2;i++) if (!dfs[i]) Tarjan(i);
        for (int i=1;i<=n;i++) {
            for (int j=1;j<=m;j++) {
                if ((~id[i][j]) && (mth[j] == i || num[i] == num[m+j])) putchar('0');
                else putchar('1');
            } putchar('\n');
        }
    }
    return 0;
}

【BZOJ 1123】[POI2008] BLO

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

就是求一求BCC
在求BCC的时候顺便统计一下答案

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

const int N = 100000+9;
const int M = 1000000+9;

int n,m,head[N],nxt[M],to[M],sz[N];
int lowlink[N],num[N],bcc_cnt,num_cnt; 
LL vout[N];
vector<int> bcc_num[N];
stack<int> stk;

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

void Tarjan(int w, int f) {
	lowlink[w] = num[w] = ++num_cnt;
	stk.push(w); sz[w] = 1; int tmp = 0;
	for (int i=head[w];i;i=nxt[i]) if (to[i] != f) {
		if (!num[to[i]]) {
			Tarjan(to[i], w);
			sz[w] += sz[to[i]];
			lowlink[w] = min(lowlink[w], lowlink[to[i]]);
			if (lowlink[to[i]] >= num[w]) {
				int cur; bcc_cnt++;
				do {
					cur = stk.top(); stk.pop();
					bcc_num[cur].push_back(bcc_cnt);
				} while (cur != to[i]);
				vout[w] += 2LL * tmp * sz[to[i]];
				tmp += sz[to[i]];
			}
		} else {
			lowlink[w] = min(num[to[i]], lowlink[w]);
		}
	}
	vout[w] += 2LL * tmp * (n - tmp - 1) + 2 * (n - 1);
}

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

int main(){
	n = read(); m = read();
	for (int i=1;i<=m;i++) {
		Add_Edge(read(),read());
	}
	Tarjan(1,1);
	for (int i=1;i<=n;i++) {
		printf("%lld\n",vout[i]);
	} 
	return 0;
}

【Codeforces 700C】Break Up

题目传送门:http://codeforces.com/problemset/problem/700/C
官方题解:http://codeforces.com/blog/entry/46283

最开始,瞄一眼:“这™不狼抓兔子吗?”
于是死坑在网络流上
发现,网络流只能保证总费用最小,但实在是保证不了边数最小
比如这个图:34167845631254
于是还是按照官方给的题解,码的求割顶的代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdio>
#include<cmath>
#include<queue>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

const int N = 1000+9;
const int M = 60000+9;
const int INF = 0x7fffffff;

int n,m,s,t,vout=INF,vis[N],tag[M],tot,sign,upd;
int head[N],nxt[M],to[M],val[M],link[N],num[N];
 queue<int> que,path,ans;

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

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

bool DFS(int w){
	if (w == t) return 1; else vis[w] = 1;
	for (int i=head[w];i;i=nxt[i]) if (!vis[to[i]]) 
		if (DFS(to[i])) {path.push(i); return 1;}
	return 0;
}

int Get_Cut(int w, int f){
	if (!num[w]) link[w] = num[w] = ++tot; int ret = w==t?1:0;
	for (int i=head[w];i;i=nxt[i]) if (!tag[i] && (i^1) != f) {
		if (num[to[i]]) link[w] = min(link[w],num[to[i]]);
		else {
			int tmp = Get_Cut(to[i],i);
			if (link[to[i]] > num[w]) {if (tmp && (upd==INF || val[upd] > val[i])) upd = i;} 
			else link[w] = min(link[w], link[to[i]]);
			ret |= tmp;
		}
	}
	return ret;
}

inline bool BFS(){
	memset(vis,0,sizeof(vis));
	que.push(s); vis[s] = 1;
	
	while (!que.empty()) {
		int w = que.front(); que.pop();
		for (int i=head[w];i;i=nxt[i]) if (!tag[i]) 
			if (!vis[to[i]]) vis[to[i]] = 1, que.push(to[i]);
	} 
	return vis[t];
}

inline void update(int a, int b){
	if (vout > val[a] + val[b]) {
		vout = val[a] + val[b];
		while (!ans.empty()) ans.pop(); 
		ans.push(a); if (b) ans.push(b);
	}
}

int main(){
	n = read(); m = read(); s = read(); t = read();
	for (int i=1,u,v,w;i<=m;i++) u=read(), v=read(), w=read(), AddEdge(u,v,w);
	if (DFS(s)) {
		while (!path.empty()) {
			int w = path.front(); 
			tag[w] = tag[w^1] = 1;
			if (BFS()) {
				memset(link,0,sizeof(link)); 
				memset(num,0,sizeof(num)); upd = INF;
				link[s] = num[s] = tot = 1; Get_Cut(s,-1);
				if (upd != INF) update(upd,w);
			} else update(w,0);
			tag[w] = tag[w^1] = 0; path.pop();
		}
		if (vout == INF) cout<<-1;
		else {
			cout<<vout<<endl<<ans.size()<<endl;
			while (!ans.empty()) cout<<ans.front()/2<<' ', ans.pop();
		}
	} else cout<<0<<endl<<0;	
	return 0;
}

【BZOJ 2438】[中山市选2011] 杀人游戏

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2438
数据生成器:http://paste.ubuntu.com/19584806/
PS:此题的随机数据不容易拍出错QAQ

来练习Tarjan的scc,然而此题细节比较多,被卡了好久QAQ

很明显,如果一个scc中知道了一个点,则其他点都可以安全推出
所以我们只需要搞出入度为零的scc有多少个即可

然而还有一个坑:
如果最后问得只剩一个单独的点了,这个点是不需要询问的
所以遇到这种单独的点,并且他连向的点的入度都不为一的话,ans -= 1

#include<iostream>
#include<cstdio>
#include<vector>
#include<stack>
using namespace std;

const int MAXN = 300000+9;

int n,m,to[MAXN],nxt[MAXN],head[MAXN];
int num[MAXN],lowlink[MAXN],in[MAXN],vout;
int scc_num[MAXN],scc_sz[MAXN],scc_cnt;
stack<int> sta;

inline void AddEdge(int u, int v){
	static int T = 0; 
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
}

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

void DFS(int w) {
	static int tot = 0; sta.push(w);
	num[w] = lowlink[w] = ++tot;
	for (int i=head[w];i;i=nxt[i]) {
		if (!num[to[i]]) DFS(to[i]), lowlink[w] = min(lowlink[w], lowlink[to[i]]);
		else if (!scc_num[to[i]]) lowlink[w] = min(lowlink[w], lowlink[to[i]]);
	}
	if (lowlink[w] == num[w]) {
		scc_cnt += 1;
		while (true) {
			int nw = sta.top(); sta.pop();
			scc_num[nw] = scc_cnt;
			scc_sz[scc_cnt]++;
			if (nw == w) break;
		}
	}
}

int main(){
	n = read(); m = read(); if (n==1) {printf("1.000000\n"); return 0;}
	for (int i=1,u,v;i<=m;i++) u = read(), v = read(), AddEdge(u,v); 
	for (int i=1;i<=n;i++) if (!num[i]) DFS(i);
	for (int i=1;i<=n;i++) for (int j=head[i];j;j=nxt[j])
		if (scc_num[to[j]] != scc_num[i]) in[scc_num[to[j]]]++;
	for (int i=1;i<=scc_cnt;i++) if (!in[i]) vout++; 
	for (int i=1,tag=0;i<=n;i++,tag=0) if (scc_sz[scc_num[i]] == 1 && !in[scc_num[i]]) {
		for (int j=head[i];j;j=nxt[j]) if (in[scc_num[to[j]]] == 1 && scc_num[to[j]] != scc_num[i]) {tag = 1; break;}
		if (!tag) {vout--; break;}
	}
	printf("%.6lf\n",1.0-(double)vout/n);
	return 0;
} 

为了学习仙人掌才来看的这个,然而现在发现仙人掌用的是无向图的TarjanQAQ