「BZOJ2730」[HNOI2012] 矿场搭建
Description
煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。
Input
输入文件有若干组数据，每组数据的第一行是一个正整数 N（N≤500），表示工地的隧道数，接下来的 N 行每行是用空格隔开的两个整数 S 和 T，表示挖 S 与挖煤点 T 由隧道直接连接。输入数据以 0 结尾。
Output
输入文件中有多少组数据，输出文件 output.txt 中就有多少行。每行对应一组输入数据的 结果。其中第 i 行以 Case i: 开始（注意大小写，Case 与 i 之间有空格，i 与:之间无空格，: 之后有空格），其后是用空格隔开的两个正整数，第一个正整数表示对于第 i 组输入数据至少需 要设置几个救援出口，第二个正整数表示对于第 i 组输入数据不同最少救援出口的设置方案总 数。输入数据保证答案小于 2^64。输出格式参照以下输入输出样例。
Sample Input
9
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0
1 3
4 1
3 5
1 2
2 6
1 5
6 3
1 6
3 2
6
1 2
1 3
2 4
2 5
3 6
3 7
0
Sample Output
Case 1: 2 4
Case 2: 4 1
Case 2: 4 1
HINT
Case 1 的四组解分别是(2,4),(3,4),(4,5),(4,6)；
Case 2 的一组解为(4,5,6,7)。
题解
由于数据范围小，此题可以暴力。。。
显然若非割点坍塌，就无所谓啦，只要考虑坍塌在割点的情况
删去所有割点得到若干连通块，如果图中只有一个连通块，一共只需要设两个
若一个连通块可以到达两个割点的话则不用设置救援出口，否则要设置一个
割点可以删去点然后遍历图求，复杂度n方
对每个割点划分的各个连通块染色，重复染色记为-1
似乎这全是暴力。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<algorithm> #include<queue> #include<cmath> #include<map> #include<queue> #define mod 1000000001 #define inf 2000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll ans; int T,n,m,cnt,tot,K; int t[505],id[505],last[505]; bool cut[505],vis[505]; struct data{int to,next,v;}e[1005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt; } void dfs(int x) { vis[x]=1; for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]&&e[i].to!=K) { vis[e[i].to]=1; dfs(e[i].to); } } void dfs2(int x) { vis[x]=1; if(!id[x])id[x]=K; else id[x]=-1; for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]&&!cut[e[i].to]) dfs2(e[i].to); } int main() { while(scanf("%d",&m)) { if(m==0)return 0; T++;printf("Case %d: ",T); n=0;cnt=0;tot=0;ans=1; memset(last,0,sizeof(last)); memset(cut,0,sizeof(cut)); memset(id,0,sizeof(id)); memset(t,0,sizeof(t)); for(int i=1;i<=m;i++) { int u=read(),v=read(); n=max(u,n);n=max(v,n); insert(u,v); } for(K=1;K<=n;K++) { memset(vis,0,sizeof(vis)); dfs(K%n+1); for(int i=1;i<=n;i++) if(!vis[i]&&i!=K) { cut[K]=1; break; } } K=0; for(int x=1;x<=n;x++) if(cut[x]) { memset(vis,0,sizeof(vis)); for(int i=last[x];i;i=e[i].next) if(!vis[e[i].to]&&!cut[e[i].to]) { K++;dfs2(e[i].to); } } for(int i=1;i<=n;i++) if(id[i]!=-1) t[id[i]]++; for(int i=1;i<=K;i++) if(t[i]!=0)tot++,ans*=t[i]; if(!tot)printf("2 %d\n",n*(n-1)/2); else printf("%d %lld\n",tot,ans); } return 0; } |
计数器 9364587
OI 课件=>
OI 课件=>
黄学长，空间里的音乐能不能换成之前的，还是之前的好听啊