专题链接
关于tarjan A - Network of Schools
原题地址
关于tarjan A - Network of Schools
原题地址
本题有2个问题，第一个是要算最少要给多少个点软件，才能使所有点都可以收到副本
第二个是要算最少加多少条边，使得图变成强连通
1：tarjan求强连通，然后缩点，计算入度为0的强连通分量
2：设现在有a个入度为0的点，b个出度为0的点（缩完点后的点），最合理的加边方法肯定是从出度为0的点向入度为0的点添加有向边，
如果a > b, 添加a条边，所有点的入度都大于0，所有点的出度也大于0，问题解决，答案是a
如果 a <= b，添加a条边，所有点入度大于0，但是还有b-a个点，它们的出度是0，所以还要再加b-a条边，所以答案是b
综合两种情况，答案是max（a，b）
当然如果图原来就是强连通的话，输出就是1 和 0 了
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
struct node
{
int next;
int to;
}edge[N * N];
int st[N];
int tot, ord, sccnum, top;
int head[N];
int low[N];
int DFN[N];
int in_deg[N];
int out_deg[N];
int block[N];
bool instack[N];
void addedge(int from, int to)
{
edge[tot].to = to;
edge[tot].next = head[from];
head[from] = tot++;
}
void tarjan (int u)
{
DFN[u] = low[u] = ++ord;
instack[u] = 1;
st[top++] = u;
for (int i = head[u]; ~i; i = edge[i].next)
{
int v = edge[i].to;
if (DFN[v] == -1)
{
tarjan (v);
if (low[u] > low[v])
{
low[u] = low[v];
}
}
else if (instack[v])
{
low[u] = min(low[u], DFN[v]);
}
}
int v;
if (DFN[u] == low[u])
{
sccnum++;
do
{
v = st[--top];
block[v] = sccnum;
instack[v] = 0;
}while (v != u);
}
}
void init ()
{
memset (DFN, -1, sizeof(DFN));
memset (low, 0, sizeof(low));
memset (head, -1, sizeof(head));
memset (in_deg, 0, sizeof(in_deg));
memset (out_deg, 0, sizeof(out_deg));
memset (instack, 0, sizeof(instack));
top = 0;
tot = 0;
sccnum = 0;
ord = 0;
}
void solve (int n)
{
for (int i = 1; i <= n; ++i)
{
if (DFN[i] == -1)
{
tarjan (i);
}
}
if (sccnum == 1)
{
printf("1\n0\n");
return;
}
for (int u = 1; u <= n; ++u)
{
for (int j = head[u]; ~j; j = edge[j].next)
{
int v = edge[j].to;
if (block[u] == block[v])
{
continue;
}
out_deg[block[u]]++;
in_deg[block[v]]++;
}
}
int a, b;
a = 0;
b = 0;
for (int i = 1; i <= sccnum; ++i)
{
if (in_deg[i] == 0)
{
a++;
}
else if (out_deg[i] == 0)
{
b++;
}
}
printf("%d\n", a);
printf("%d\n", max(a, b));
}
int main()
{
int n;
int u, v;
while (~scanf("%d", &n))
{
init();
for (int u = 1; u <= n; ++u)
{
while (scanf("%d", &v), v)
{
addedge (u, v);
}
}
solve(n);
}
return 0;
}
B - Network
原题地址
求割点数目，模版题
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
struct node
{
int next;
int to;
}edge[N * N];
bool instack[N];
bool cut[N];
int head[N];
int DFN[N];
int low[N];
int cnt, tot, ord, root;
void addedge (int from, int to)
{
edge[tot].to = to;
edge[tot].next = head[from];
head[from] = tot++;
}
void tarjan (int u, int fa)
{
DFN[u] = low[u] = ++ord;
instack[u] = 1;
int cnt = 0;
for (int i = head[u]; ~i; i = edge[i].next)
{
int v = edge[i].to;
if (v == fa)
{
continue;
}
if (DFN[v] == -1)
{
tarjan(v, u);
cnt++;
if (low[u] > low[v])
{
low[u] = low[v];
}
if (root == u && cnt > 1)
{
cut[u] = 1;
}
else if (u != root && low[v] >= DFN[u])
{
cut[u] = 1;
}
}
else if (instack[v])
{
low[u] = min(low[u], DFN[v]);
}
}
}
void init ()
{
memset (DFN, -1, sizeof(DFN));
memset (low, 0, sizeof(low));
memset (instack, 0, sizeof(instack));
memset (cut, 0, sizeof(cut));
memset (head, -1, sizeof(head));
tot = 0;
ord = 0;
}
void solve (int n)
{
root = 1;
tarjan (1, -1);
int ans = 0;
for (int i = 1; i <= n; ++i)
{
if (cut[i])
{
ans++;
}
}
printf("%d\n", ans);
}
int main()
{
int n;
int u, v;
while (~scanf("%d", &n), n)
{
init();
while (scanf("%d", &u), u)
{
while (getchar() != '\n')
{
scanf("%d", &v);
addedge (u, v);
addedge (v, u);
}
}
solve(n);
}
return 0;
}
C - Critical Links
求桥，模版题，这题似乎不用判重边
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
const int M = (N << 2);
struct node
{
int next;
int to;
// int id;
}edge[M];
struct BRIDGE
{
int u;
int v;
}bridge[M];
int head[N];
int DFN[N];
int low[N];
int st[N];
bool instack[N];
int tot, top, ord, sccnum, cnt;
void init ()
{
memset (head, -1, sizeof(head));
memset (DFN, -1, sizeof(DFN));
memset (low, 0, sizeof(low));
memset (instack, 0, sizeof(instack));
tot = top = cnt = sccnum = ord = 0;
}
void addedge (int from, int to)
{
edge[tot].to = to;
// edge[tot].id = id;
edge[tot].next = head[from];
head[from] = tot++;
}
int cmp (BRIDGE a, BRIDGE b)
{
if (a.u == b.u)
{
return a.v < b.v;
}
return a.u < b.u;
}
void tarjan (int u, int fa)
{
DFN[u] = low[u] = ++ord;
instack[u] = 1;
st[top++] = u;
for (int i = head[u]; ~i; i = edge[i].next)
{
int v = edge[i].to;
if (v == fa)
{
continue;
}
if (DFN[v] == -1)
{
tarjan (v, u);
low[u] = min (low[v], low[u]);
if (low[v] > DFN[u])
{
bridge[++cnt].u = u;
bridge[cnt].v = v;
if (bridge[cnt].u > bridge[cnt].v)
{
swap (bridge[cnt].u, bridge[cnt].v);
}
}
}
else if (instack[v])
{
low[u] = min (low[u], DFN[v]);
}
}
if (low[u] == DFN[u])
{
++sccnum;
int v;
do
{
v = st[--top];
instack[v] = 0;
}while (u != v);
}
}
void solve (int n)
{
for (int i = 1; i <= n; ++i)
{
if (DFN[i] == -1)
{
tarjan(i, -1);
}
}
sort (bridge + 1, bridge + cnt + 1, cmp);
printf("%d critical links\n", cnt);
for (int i = 1; i <= cnt; ++i)
{
printf("%d - %d\n", bridge[i].u - 1, bridge[i].v - 1);
}
printf("\n");
}
int main()
{
int n;
int u, v;
int num;
while (~scanf("%d", &n))
{
if (n == 0)
{
printf("0 critical links\n\n");
continue;
}
init();
for (int i = 1; i <= n; ++i)
{
scanf("%d", &u);
++u;
getchar();
getchar();
scanf("%d", &num);
getchar();
while (num--)
{
scanf("%d", &v);
++v;
addedge (u, v);
}
}
solve (n);
}
return 0;
}
D - Network
原题地址
敢不敢不叫 Network了
询问每次添加一条边以后剩下的桥的数目
先一次tarjan缩点，得到一颗树，每次 加边，两个端点到它们的lca之间的边都不再是桥，所以每一次我们都可以通过暴力求出lca，然后统计出少了多少条桥，但是暴力统计时，会遇到某些边在之前就不是桥的情况，我们用并查集来跳过这些边（每一次加边就把lca路径上的点都合并到一个集合里去，这里根用最上面的点，到时如果遇到这种点，直接可以跳到它们的根上去）
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int N = 110010;
const int M = 210010;
int head[N];
int head2[N];
int DFN[N];
int low[N];
int deep[N];
int father[N];
int block[N];
int pre[N];
int st[N];
bool instack[N];
int tot, tot2, top, ord, sccnum, icase;
struct node
{
int next;
int to;
int id;
}edge[M << 2], edge2[M << 2];
void init ()
{
memset (DFN, -1, sizeof(DFN));
memset (head, -1, sizeof(head));
memset (head2, -1, sizeof(head2));
memset (low, 0, sizeof(low));
memset (instack, 0, sizeof(instack));
tot = tot2 = ord = sccnum = top = 0;
}
void addedge (int from, int to, int id)
{
edge[tot].to = to;
edge[tot].id = id;
edge[tot].next = head[from];
head[from] = tot++;
}
void addedge2 (int from, int to)
{
edge2[tot2].to = to;
edge2[tot2].next = head2[from];
head2[from ] = tot2++;
}
void dfs (int u, int fa, int d)
{
pre[u] = fa;
deep[u] = d;
for (int i = head2[u]; ~i; i = edge2[i].next)
{
int v = edge2[i].to;
if (v == fa)
{
continue;
}
dfs (v, u, d + 1);
}
}
int find (int x)
{
if (x == father[x])
{
return x;
}
return father[x] = find(father[x]);
}
void tarjan (int u, int x)
{
DFN[u] = low[u] = ++ord;
instack[u] = 1;
st[top++] = u;
for (int i = head[u]; ~i; i = edge[i].next)
{
int v = edge[i].to;
if (edge[i].id == x)
{
continue;
}
if (DFN[v] == -1)
{
tarjan (v, edge[i].id);
low[u] = min(low[u], low[v]);
}
else if (instack[v])
{
low[u] = min(low[u], DFN[v]);
}
}
int v;
if (DFN[u] == low[u])
{
++sccnum;
do
{
v = st[--top];
instack[v] = 0;
block[v] = sccnum;
}while (v != u);
}
}
int LCA (int a, int b)
{
while (a != b)
{
if (deep[a] > deep[b])
{
a = pre[a];
}
else if (deep[a] < deep[b])
{
b = pre[b];
}
else
{
a = pre[a];
b = pre[b];
}
a = find(a);
b = find(b);
}
return a;
}
void solve (int n)
{
tarjan (1, -1);
for (int u = 1; u <= n; ++u)
{
for (int i = head[u]; ~i; i = edge[i].next)
{
int v = edge[i].to;
if (block[u] == block[v])
{
continue;
}
addedge2 (block[u], block[v]);
}
}
for (int i = 1; i <= sccnum; ++i)
{
father[i] = i;
}
int cnt = sccnum - 1;
dfs(1, -1, 0);
int q, a, b, lca;
scanf("%d", &q);
printf("Case %d:\n", icase++);
while (q--)
{
scanf("%d%d", &a, &b);
a = block[a];
b = block[b];
if (a == b)
{
printf("%d\n", cnt);
continue;
}
a = find(a);
b = find(b);
lca = LCA (a, b);
int x = 0;
while (a != lca)
{
++x;
father[a] = lca;
a = pre[a];
a = find(a);
}
while (b != lca)
{
++x;
father[b] = lca;
b = pre[b];
b = find(b);
}
cnt -= x;
printf("%d\n", cnt);
}
}
int main()
{
int n, m;
int u, v;
icase = 1;
while (~scanf("%d%d", &n, &m))
{
if (!n && !m)
{
break;
}
init();
for (int i = 1; i <= m; ++i)
{
scanf("%d%d", &u, &v);
addedge (u, v, i);
addedge (v, u, i);
}
solve(n);
printf("\n");
}
return 0;
}
E - Redundant Paths
原题地址
求桥的数目，模版题，注意重边的判定
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5010;
const int M = 10010;
struct node
{
int next;
int to;
int id;
}edge[M << 1];
int head[N];
int DFN[N];
int low[N];
bool instack[N];
int block[N];
int deg[N];
stack <int> st;
int tot, sccnum, ord;
void addedge (int from, int to, int id)
{
edge[tot].id = id;
edge[tot].to = to;
edge[tot].next = head[from];
head[from] = tot++;
}
void init ()
{
memset (DFN, -1, sizeof(DFN));
memset (low, 0, sizeof(low));
memset (instack, 0, sizeof(instack));
memset (deg, 0, sizeof(deg));
memset (head, -1, sizeof(head));
while (!st.empty())
{
st.pop();
}
tot = sccnum = ord = 0;
}
void tarjan (int u, int x)
{
DFN[u] = low[u] = ++ord;
instack[u] = 1;
st.push(u);
for (int i = head[u]; ~i; i = edge[i].next)
{
int v = edge[i].to;
if (x == edge[i].id)
{
continue;
}
if (DFN[v] == -1)
{
tarjan (v, edge[i].id);
low[u] = min(low[u], low[v]);
}
else if (instack[v])
{
low[u] = min(low[u], DFN[v]);
}
}
int v;
if (DFN[u] == low[u])
{
++sccnum;
do
{
v = st.top();
st.pop();
instack[v] = 0;
block[v] = sccnum;
}while (v != u);
}
}
void solve (int n)
{
for (int i = 1; i <= n; ++i)
{
if (DFN[i] == -1)
{
tarjan (i, -1);
}
}
for (int u = 1; u <= n; ++u)
{
for (int j = head[u]; ~j; j = edge[j].next)
{
int v = edge[j].to;
if (block[u] == block[v])
{
continue;
}
++deg[block[u]];
++deg[block[v]];
}
}
int cnt = 0;
for (int i = 1; i <= sccnum; ++i)
{
if (deg[i] / 2 == 1)
{
++cnt;
}
}
printf("%d\n", (cnt + 1) >> 1);
}
int main()
{
int n, m;
int u, v;
while (~scanf("%d%d", &n, &m))
{
init();
for (int i = 1; i <= m; ++i)
{
scanf("%d%d", &u, &v);
addedge (u, v, i);
addedge (v, u, i);
}
solve(n);
}
return 0;
}
F - Warm up
原题地址
询问如何加一条边，使得剩下的桥的数目最少，输出数目
我的做法是先tarjan缩点，得到树，然后求出树的直径，把边加在直径的两端，减少的桥肯定是最多的
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int N = 200010;
const int inf = 0x3f3f3f3f;
const int M = 3000010;
struct node
{
int next;
int to;
int id;
}edge[M], edge2[M];
bool vis[N];
bool flag[N];
int dist[N];
int head[N];
int head2[N];
int low[N];
int block[N];
int DFN[N];
bool instack[N];
stack<int>qu;
int br_cnt, n, m, end_p;
int tot, tot2, maxs, index, top, sccnum;
void addedge(int from, int to, int id)
{
edge[tot].id = id;
edge[tot].to = to;
edge[tot].next = head[from];
head[from] = tot++;
}
void addedge2(int from, int to)
{
edge2[tot].to = to;
edge2[tot].next = head2[from];
head2[from] = tot++;
}
void init()
{
index = 0;
sccnum = 0;
top = 0;
tot = 0;
tot2 = 0;
maxs = 0;
br_cnt = 0;
end_p = 0;
memset ( head, -1, sizeof(head) );
memset (head2, -1, sizeof(head2) );
memset ( low, 0, sizeof(low) );
memset (DFN, 0, sizeof(DFN) );
memset ( instack, 0, sizeof(instack) );
memset ( flag, 0, sizeof(flag) );
memset (vis, 0, sizeof(vis) );
}
void build()
{
int u, v;
while (!qu.empty() )
{
qu.pop();
}
for (int i = 1; i <= m; ++i)
{
scanf("%d%d", &u, &v);
addedge(u, v, i);
addedge(v, u, i);
}
}
void tarjan(int u, int fa)
{
qu.push(u);
instack[u] = 1;
DFN[u] = low[u] = ++index;
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if (fa == edge[i].id)
{
continue;
}
if ( !instack[v] )
{
tarjan(v, edge[i].id);
low[u] = min(low[u], low[v]);
if (DFN[u] < low[v])
{
br_cnt++;
}
}
else
{
low[u] = min(DFN[v], low[u]);
}
}
if (DFN[u] == low[u])
{
sccnum++;
int v;
while(1)
{
v = qu.top();
qu.pop();
instack[v] = 0;
block[v] = sccnum;
if(v == u)
{
break;
}
}
}
}
void bfs(int s)
{
queue<int>qu;
while ( !qu.empty() )
{
qu.pop();
}
memset ( vis, 0, sizeof(vis) );
qu.push(s);
dist[s] = 0;
vis[s] = 1;
maxs = 0;
while ( !qu.empty() )
{
int u = qu.front();
qu.pop();
for (int i = head2[u]; i != -1; i = edge2[i].next)
{
int v = edge2[i].to;
if (!vis[v])
{
vis[v] = 1;
dist[v] = dist[u] + 1;
qu.push(v);
if (maxs < dist[v])
{
maxs = dist[v];
end_p = v;
}
}
}
}
}
void solve()
{
for (int i = 1; i <= n; ++i)
{
if (DFN[i] == 0)
{
tarjan(i, -1);
}
}
for (int u = 1; u <= n; ++u)
{
for (int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if (block[u] != block[v])
{
addedge2(block[u], block[v]);
}
}
}
bfs(1);
bfs(end_p);
printf("%d\n", br_cnt - maxs);
}
int main()
{
while (~scanf("%d%d", &n, &m))
{
if (!n && !m)
{
break;
}
init();
build();
solve();
}
return 0;
}
G - Strongly connected
原题地址
求最多可以加多少边，使得最新的图不是强连通图
最终情况一定是再加一条边，整张图就是强连通的了，那么我们可以把图看成2部分x和y，x和y都是完全图，然后x每个点到y每个点都有边，但是y到x没有边，如果有肯定是强连通了，设x中有a个点，y中有b个点 则 a + b = n
则边数就是 a * (a - 1) + b * (b - 1) + a * b - m，化简得到：n * n - a * b - n - m;
如何让这个值大那就是如何选取x和y的问题了，显然a和b差距越大越好，那么就可以通过tarajan来找出一个包含点最少的强连通分量来当x，其他的强连通分量作为y，这样就很容易了
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
struct node
{
int next;
int to;
}edge[N << 1];
int head[N];
int DFN[N];
int low[N];
int num[N];
int st[N];
bool instack[N];
int block[N];
int in[N];
int out[N];
int tot, top, ord, sccnum;
void addedge (int from, int to)
{
edge[tot].to = to;
edge[tot].next = head[from];
head[from] = tot++;
}
void init ()
{
memset (num, 0, sizeof(num));
memset (in, 0, sizeof(in));
memset (out, 0, sizeof(out));
memset (head, -1, sizeof(head));
memset (DFN, -1, sizeof(DFN));
memset (low, 0, sizeof(low));
memset (instack, 0, sizeof(instack));
tot = top = ord = sccnum = 0;
}
void tarjan (int u)
{
DFN[u] = low[u] = ++ord;
instack[u] = 1;
st[top++] = u;
for (int i = head[u]; ~i; i = edge[i].next)
{
int v = edge[i].to;
if (DFN[v] == -1)
{
tarjan (v);
low[u] = min (low[u], low[v]);
}
else if (instack[v])
{
low[u] = min(low[u], DFN[v]);
}
}
if (DFN[u] == low[u])
{
int v;
++sccnum;
do
{
++num[sccnum];
v = st[--top];
block[v] = sccnum;
instack[v] = 0;
}while (v != u);
}
}
void solve (int n, int m)
{
for (int i = 1; i <= n; ++i)
{
if (DFN[i] == -1)
{
tarjan (i);
}
}
if (sccnum == 1)
{
printf("-1\n");
return;
}
for (int u = 1; u <= n; ++u)
{
for (int i = head[u]; ~i; i = edge[i].next)
{
int v = edge[i].to;
if (block[u] == block[v])
{
continue;
}
++out[block[u]];
++in[block[v]];
}
}
long long ans = 0;
long long ret = (long long)(n * n - n - m);
for (int i = 1; i <= sccnum; ++i)
{
if (in[i] == 0 || out[i] == 0)
{
ans = max(ans, ret - (long long)(num[i] * (n - num[i])));
}
}
printf("%lld\n", ans);
}
int main()
{
int t;
int n, m;
int u, v;
int icase = 1;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
init();
for (int i = 1; i <= m; ++i)
{
scanf("%d%d", &u, &v);
addedge (u, v);
}
printf("Case %d: ", icase++);
solve (n, m);
}
return 0;
}
H - Prince and Princess
原题地址
首先做一次最大匹配，设为cnt，那么对于左边，有n-cnt个王子没有匹配，对于右边，有m-cnt个公主没有匹配，所以我们在左边加上m-cnt个虚拟点，这些点喜欢所有公主，右边加上n-cnt个虚拟点，这些点被所有王子喜欢，这样左右两边都是n+m-cnt个点，在求一次最大匹配，这一定是一个完备匹配，对于每一个王子，用他目前匹配的公主，向所有他喜欢的公主连一条有向边，这表示单方面可以替换，所以再对得到的新图求强连通，处在一个强连通分量的公主可以相互替换
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1100;
int head[N];
int DFN[N];
int low[N];
int block[N];
int match[N];
int match2[N];
bool used[N];
bool instack[N];
bool g[N][N];
stack <int> st;
vector <int> vis;
int n, m, tot, sccnum, ord, num_v, num_u;
struct node
{
int next;
int to;
}edge[N * N * 5];
void init ()
{
vis.clear();
memset (g, 0, sizeof(g));
memset (match, -1, sizeof(match));
memset (match2, -1, sizeof(match2));
memset (used, 0, sizeof(used));
memset (instack, 0, sizeof(instack));
memset (DFN, -1, sizeof(DFN));
memset (low, 0, sizeof(low));
memset (head, -1, sizeof(head));
tot = sccnum = ord = 0;
}
void addedge (int from, int to)
{
edge[tot].to = to;
edge[tot].next = head[from];
head[from] = tot++;
}
bool dfs (int u)
{
for (int i = 1; i <= num_v; ++i)
{
if (!g[u][i])
{
continue;
}
int v = i;
if (!used[v])
{
used[v] = 1;
if (match[v] == -1 || dfs (match[v]))
{
match[v] = u;
return 1;
}
}
}
return 0;
}
int hungry ()
{
int cnt = 0;
for (int i = 1; i <= num_u; ++i)
{
memset (used, 0, sizeof(used));
if (dfs(i))
{
++cnt;
}
}
return cnt;
}
void tarjan (int u)
{
DFN[u] = low[u] = ++ord;
instack[u] = 1;
st.push(u);
for (int i = head[u]; ~i; i = edge[i].next)
{
int v = edge[i].to;
if (DFN[v] == -1)
{
tarjan (v);
low[u] = min (low[v], low[u]);
}
else if (instack[v])
{
low[u] = min (low[u], DFN[v]);
}
}
int v;
if (low[u] == DFN[u])
{
++sccnum;
do
{
v = st.top();
st.pop();
instack[v] = 0;
block[v] = sccnum;
}while (u != v);
}
}
void solve ()
{
num_u = n;
num_v = m;
int cnt = hungry();
num_u = n + m - cnt;
num_v = num_u;
for (int i = n + 1; i <= num_u; ++i)
{
for (int j = 1; j <= num_v; ++j)
{
g[i][j] = 1;
}
}
for (int i = 1; i <= num_u; ++i)
{
for (int j = m + 1; j <= num_v; ++j)
{
g[i][j] = 1;
}
}
// printf("%d\n", cnt);
memset (match, -1, sizeof(match));
cnt = hungry();
// printf("%d\n", cnt);
for (int i = 1; i <= num_v; ++i)
{
match2[match[i]] = i;
}
for (int i = 1; i <= num_u; ++i)
{
for (int j = 1; j <= num_v; ++j)
{
if (g[i][j] && match2[i] != j)
{
addedge (match2[i], j);
}
}
}
for (int i = 1; i <= num_v; ++i)
{
if (DFN[i] == -1)
{
tarjan (i);
}
}
for (int i = 1; i <= n; ++i)
{
vis.clear();
for (int j = 1; j <= m; ++j)
{
if (g[i][j] && block[j] == block[match2[i]])
{
vis.push_back (j);
}
}
int tmp = vis.size();
printf("%d", tmp);
for (int j = 0; j < tmp; ++j)
{
printf(" %d", vis[j]);
}
printf("\n");
}
}
int main ()
{
int t;
int u, v, num;
int icase = 1;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
init();
for (int i = 1; i <= n; ++i)
{
scanf("%d", &num);
while (num--)
{
scanf("%d", &v);
g[i][v] = 1;
}
}
printf("Case #%d:\n", icase++);
solve();
}
return 0;
}
I - Caocao's Bridges
原题地址
此题其实不难，但是很坑
1：如果图不连通，那么不需要派人去
2：如果有一条桥，防卫兵数目为0，那么应该派1个人去
3：重边判定
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
const int M = N * N;
struct node
{
int next;
int to;
int id;
int w;
}edge[M << 1];
int head[N];
int DFN[N];
int low[N];
int st[N];
bool instack[N];
int bridge[M];
int tot, cnt, ord, top, sccnum;
void addedge (int from, int to, int id, int w)
{
edge[tot].w = w;
edge[tot].to = to;
edge[tot].id = id;
edge[tot].next = head[from];
head[from] = tot++;
}
void init ()
{
memset (head, -1, sizeof(head));
memset (DFN, -1, sizeof(DFN));
memset (low, 0, sizeof(low));
memset (instack, 0, sizeof(instack));
tot = cnt = ord = top = sccnum = 0;
}
void tarjan (int u, int x)
{
DFN[u] = low[u] = ++ord;
instack[u] = 1;
st[top++] = u;
for (int i = head[u]; ~i; i = edge[i].next)
{
int v = edge[i].to;
if (edge[i].id == x)
{
continue;
}
if (DFN[v] == -1)
{
tarjan (v, edge[i].id);
low[u] = min(low[u], low[v]);
if (low[v] > DFN[u])
{
bridge[++cnt] = edge[i].w;
}
}
else if (instack[v])
{
low[u] = min(low[u], DFN[v]);
}
}
int v;
if (DFN[u] == low[u])
{
++sccnum;
do
{
v = st[--top];
instack[v] = 0;
}while (u != v);
}
}
void solve (int n)
{
int num = 0;
for (int i = 1; i <= n; ++i)
{
if (DFN[i] == -1)
{
++num;
tarjan (i, -1);
}
if (num > 1)
{
break;
}
}
if (num > 1)
{
printf("0\n");
return;
}
if (cnt == 0)
{
printf("-1\n");
return;
}
int minx = 0x3f3f3f3f;
for (int i = 1; i <= cnt; ++i)
{
if (minx > bridge[i])
{
minx = bridge[i];
}
}
if (minx == 0)
{
++minx;
}
printf("%d\n", minx);
}
int main()
{
int n, m;
int u, v, w;
while (~scanf("%d%d", &n, &m))
{
if (!n && !m)
{
break;
}
init();
for (int i = 1; i <= m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
addedge (u, v, i, w);
addedge (v, u, i, w);
}
solve(n);
}
return 0;
}