题目大意

题目是图片形式的,就简要说下题意算了

一个有向图 G=(V, E) 称为半连通的(Semi-Connected),如果满足图中任意两点 u v,存在一条从 u 到 v 的路径或者从 v 到 u 的路径

给一个有向图(n 个点,m 条边),求出她的最大半连通子图中所包含的点数,以及这样的最大半连通子图有多少个(要求模上一个给定的数 x)

对于20%的数据, N ≤18;

对于60%的数据, N ≤10000;

对于100%的数据, N ≤100000, M ≤1000000;

对于100%的数据, X ≤10^8。

做法分析

这种题目在 POJ 做过类似的:POJ 2762 Going from u to v or from v to u?,它只是询问一个图是否是半连通的,解题报告

这题其实也差不多的做法,先缩点,重新建图,使其成为一个 DAG,DAG 中每个点有一个点权表示这个点是原图中的几个点缩成的

新图中的一个最大半连通子图,必然是新图中的一个最长链(点权和最大),知道了这点之后,DP 就行了,类似于树形 DP,先求出从每个点出发,能走的最长链是多长,统计最长的那条就是最大半连通子图的点的数量了,至于怎么求有多少个最大半连通子图,也是一样的 DP 就行,在上一步的 DP 之后,再 DP 一遍,统计每个点出发能走出多少条最长链,最后统计求和即可

参考代码

 #include <iostream>
#include <cstring>
#include <cstdio>
#include <stack>
#include <vector>
#include <set> using namespace std; const int N=; set <pair<int, int> > tub;
stack <int> S;
vector <int> arc[N], adj[N];
int n, m, x, ans1, ans2, T, ind;
int id[N], low[N], dfn[N], cnt[N];
bool vs[N]; void tarjan(int u) {
dfn[u]=low[u]=T++;
S.push(u), vs[u]=;
for(int i=, len=(int)adj[u].size(); i<len; i++) {
int v=adj[u][i];
if(dfn[v]==-) {
tarjan(v);
if(low[u]>low[v]) low[u]=low[v];
}
else if(vs[v] && low[u]>dfn[v]) low[u]=dfn[v];
}
if(low[u]==dfn[u]) {
while() {
int v=S.top();
S.pop(), vs[v]=;
id[v]=ind, cnt[ind]++;
if(v==u) break;
}
ind++;
}
} void DFS1(int u) {
vs[u]=;
for(int i=, len=(int)arc[u].size(); i<len; i++) {
int v=arc[u][i];
if(!vs[v]) DFS1(v);
dfn[u]=max(dfn[u], dfn[v]);
}
dfn[u]+=cnt[u];
} void DFS2(int u) {
vs[u]=;
for(int i=, len=(int)arc[u].size(); i<len; i++) {
int v=arc[u][i];
if(!vs[v]) DFS2(v);
if(dfn[u]==cnt[u]+dfn[v]) id[u]=(id[u]+id[v])%x;
}
if((int)arc[u].size()==) id[u]=;
if(dfn[u]==ans1) ans2=(ans2+id[u])%x;
} int main() {
// freopen("in", "r", stdin);
scanf("%d%d%d", &n, &m, &x);
for(int i=; i<=n; i++) adj[i].clear();
for(int i=, a, b; i<m; i++) {
scanf("%d%d", &a, &b);
adj[a].push_back(b);
}
fill(dfn, dfn++n, -);
fill(vs, vs++n, );
T=ind=;
while(!S.empty()) S.pop();
for(int i=; i<=n; i++) if(dfn[i]==-) tarjan(i);
for(int i=; i<ind; i++) arc[i].clear();
fill(low, low+ind, );
tub.clear();
for(int i=; i<=n; i++)
for(int j=, len=(int)adj[i].size(); j<len; j++) {
int v=id[adj[i][j]], u=id[i];
if(u==v) continue;
if(tub.find(make_pair(u, v))!=tub.end()) continue;
low[v]++, arc[u].push_back(v);
tub.insert(make_pair(u, v));
}
fill(vs, vs+ind, );
fill(dfn, dfn+ind, );
ans1=, ans2=;
for(int i=; i<ind; i++) if(low[i]==) {
DFS1(i);
ans1=max(ans1, dfn[i]);
}
fill(vs, vs+ind, );
fill(id, id+ind, );
for(int i=; i<ind; i++) if(low[i]==) DFS2(i);
printf("%d\n%d\n", ans1, ans2);
return ;
}

BZOJ 1093

题目链接 & AC 通道

BZOJ 1093 [ZJOI2007] 最大半连通子图

04-24 01:37