首页 > ACM题库 > HDU-杭电 > HDU 3671-Boonie and Clyde[解题报告]HOJ
2014
11-30

HDU 3671-Boonie and Clyde[解题报告]HOJ

Boonie and Clyde

问题描述 :

As two icons of the Great Depression, Bonnie and Clyde represent the ultimate criminal couple. Stories were written, headlines captured, and films were made about the two bank robbers known as Romeo and Juliet in a getaway car.

The new generation of Bonnie and Clyde is no longer cold-blooded killers with guns. Due to the boom of internet, they turn to online banks and scheme to hack the safety system. The safety system consists of a number of computers connected by bidirectional cables. Since time is limited, they decide that they will attack exactly two computers A and B in the network, and as a result, other computers won’t be able to transmit messages via A and B . The attack is considered successful if there are at least two computers (other than A and B ) that disconnected after the attack.

As they want to minimize the risk of being captured, they need to find the easiest way to destroy the safety system. However, a brief study of the network indicates that there are many ways to achieve their objective; therefore they kidnapped the computer expert, you, to help with the calculation. To simplify the problem, you are only asked to tell them how many ways there are to destroy the safety system.

输入:

There are multiple test cases in the input file. Each test case starts with two integers N (3<=N<=1000) and M (0<=M<=10000) , followed by M lines describing the connections between the N computers. Each line contains two integers A , B (1<=A, B<=N) , which indicates that computer A and B are connected by a bidirectional cable.

There is a blank line between two successive test cases. A single line with N = 0 and M = 0 indicates the end of input file.

输出:

There are multiple test cases in the input file. Each test case starts with two integers N (3<=N<=1000) and M (0<=M<=10000) , followed by M lines describing the connections between the N computers. Each line contains two integers A , B (1<=A, B<=N) , which indicates that computer A and B are connected by a bidirectional cable.

There is a blank line between two successive test cases. A single line with N = 0 and M = 0 indicates the end of input file.

样例输入:

4 4
1 2
2 3
3 4
4 1

7 9
1 2
1 3
2 3
3 4
3 5
4 5
5 6
5 7
6 7

0 0

样例输出:

Case 1: 2 
Case 2: 11

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<ctime>
using namespace std;
const int MAX=1005;
struct Bridge{int x,y;}br[1000002];
struct node
{
 int v,next;
}g[MAX*MAX];
int adj[MAX],vis[MAX],low[MAX],dfn[MAX],flag[MAX],e,n,m,index,cnt;
int set[MAX],num[MAX],bn,D[MAX];
bool cut[MAX];
void add(int u,int v)
{
 g[e].v=v; g[e].next=adj[u]; adj[u]=e++;
 g[e].v=u; g[e].next=adj[v]; adj[v]=e++;
}
void dfs(int u,int fa,int deep)
{
	int i,v;
	vis[u]=1;
	low[u]=D[u]=++index;
	int tot=0;
	for(i=adj[u];i!=-1;i=g[i].next)
	{
	 v=g[i].v;
	 if(v==fa||flag[v])
 continue;
 if(vis[v]!=0)
 low[u]=min(low[u],D[v]);
 if(vis[v]==0)
 {
 dfs(v,u,deep+1);
 tot++;
 low[u]=min(low[u],low[v]);
 if((fa==-1&&tot>1)||(fa!=-1&&low[v]>=D[u]))
 cut[u]=true;
 }
	}
 vis[u]=2;
}
int find(int x)
{
 if(set[x]!=x)
 set[x]=find(set[x]);
 return set[x];
}
bool check(int x)
{
 for(int i=1;i<=n;i++)
 {
 set[i]=i;
 num[i]=1;
 }
 for(int j=0;j<e;j+=2)
 {
 if(g[j].v==x||g[j^1].v==x)
 continue;
 int f1=find(g[j].v);
 int f2=find(g[j^1].v);
 if(f1==f2)
 continue;
 else
 {
 set[f1]=f2;
 num[f2]+=num[f1];
 }
 }
 cnt=n-1;
 int j=0;
 bool ok=false;
 for(int i=1;i<=n;i++)
 {
 int t=find(i);
 if(t==i)
 j++;
 if(num[t]==1&&i!=x)
 ok=true;
 }
 if(j==3)
 {
 if(ok)
 cnt--;
 return true;
 }
 return j>2;
}
void solve()
{
 int i,j,k;
 int ans=0;
 bn=0;
 memset(flag,0,sizeof(flag));
 for(i=1;i<=n;i++)
 {
 if(check(i))
 {
 ans+=cnt;
 continue;
 }
 memset(cut,0,sizeof(cut));
 memset(dfn,0,sizeof(dfn));
 memset(vis,0,sizeof(vis));
 memset(low,0,sizeof(low));
 memset(D,0,sizeof(D));
 index=0;
 flag[i]=1;
 if(i==1)
 dfs(2,-1,0);
 else
 dfs(1,-1,0);
 for(j=1;j<=n;j++)
 if(cut[j])
 ans++;
 flag[i]=0;
 }
 printf("%d\n",ans/2);
}
int main()
{
 int i,j,k;
 int ca=0;
 while(scanf("%d%d",&n,&m)!=EOF)
 {
 if(n==0&&m==0)
 break;
 memset(adj,-1,sizeof(adj));
 e=0;
 while(m--)
 {
 scanf("%d%d",&i,&j);
 add(i,j);
 }
 printf("Case %d: ",++ca);
 if(n<=3)
 {
 puts("0");
 continue;
 }
 solve();
 }
 return 0;
}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)