Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 190 Accepted Submission(s): 78
题解：题目问的是去掉边使图仍然联通。很简单的一道图论题，我竟然用prime错了半天。。。最后还是改了krustra,让找有多少中取法，直接暴力取边
代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<vector> using namespace std; const int INF=0x3f3f3f3f; #define mem(x,y) memset(x,y,sizeof(x)) #define SI(x) scanf("%d",&x) #define PI(x) printf("%d",x) #define SD(x,y) scanf("%lf%lf",&x,&y) #define P_ printf(" ") typedef long long LL; const int MAXN=110; int pre[MAXN]; int s[MAXN],e[MAXN]; int N,ans; int find(int r){ return pre[r]= pre[r]==r?r:find(pre[r]); } int check(int a,int b){ for(int i=1;i<=N;i++)pre[i]=i; for(int i=0;i<=N;i++){ if(i==a||i==b)continue; int f1=find(s[i]),f2=find(e[i]); //printf("%d %d\n",f1,f2); if(f1!=f2)pre[f1]=f2; } int cnt=0; for(int i=1;i<=N;i++){ if(pre[i]==i)cnt++; // if(cnt>1)printf("%d\n",cnt); if(cnt>1)return 0; } return 1; } int main(){ int T; SI(T); while(T--){ SI(N); for(int i=0;i<=N;i++) SI(s[i]),SI(e[i]); int ans=0; for(int i=0;i<=N;i++) for(int j=i;j<=N;j++){//相等代表的是取一条边。 ans+=check(i,j); } printf("%d\n",ans); } return 0; }
原文：http://www.cnblogs.com/handsomecui/p/5204388.html