Rikka with Graph

 Accepts: 123
 Submissions: 525
 Time Limit: 2000/1000 MS (Java/Others)
 Memory Limit: 65536/65536 K (Java/Others)
问题描述
众所周知，萌萌哒六花不擅长数学，所以勇太给了她一些数学问题做练习，其中有一道是这样的：

给出一张 nn 个点 n+1n+1 条边的无向图，你可以选择一些边（至少一条）删除。

现在勇太想知道有多少种方案使得删除之后图依然联通。

当然，这个问题对于萌萌哒六花来说实在是太难了，你可以帮帮她吗？
输入描述
第一行一个整数表示数据组数 T(T \leq 30)T(T≤30)。

每组数据的第一行是一个整数 n(n \leq 100)n(n≤100)。

接下来 n+1n+1 行每行两个整数 u,vu,v 表示图中的一条边。
输出描述
对每组数据输出一行一个整数表示答案。
输入样例
1

3

1 2

2 3

3 1

1 3
输出样例
9
思路：并查集，最短路，组合，先用并查集，找一到n-1条可以连通所有点的边，同时也判断了，整个图是否连通，然后剩下的2条边，分别以该边的一个点为起点
另一个位终点，用最短路搜连接这两个点的最小环由哪些边组成，然后记录个环的共同边ans，和两个环各自的边nk,mk,最后答案就是nk+mk-ans+nk*mk-ans*ans;nk+mk-ans--去掉一个边的方案，应为环去一边，所有点还是连通的。

nk*mk-ans*ans--去两个边的可能每个环出一个边方案为nk*mk，因为两个环重合的地方不能去，所以减ans*ans；
这个复杂度为（N*N）AC 0ms
  1 #include<stdio.h>

  2 #include<algorithm>

  3 #include<iostream>

  4 #include<string.h>

  5 #include<queue>

  6 #include<vector>

  7 #include<set>

  8 #include<map>

  9 #include<math.h>

 10 using namespace std;

 11 struct node

 12 {

 13     int x;

 14     int y;

 15 };

 16 vector<int>dian[110];

 17 node bian[110];

 18 bool flag[110];

 19 int bin[110];

 20 int shen[110];

 21 int dj[110];

 22 int TWO[200];

 23 int HH[110];

 24 int mapp[110][110];

 25 int ma[110][110];

 26 int pre[110];

 27 int DD[110];

 28 int CC[110];

 29 map<int,int>my;

 30 int cha(int x,int y);

 31 void dfs(int n,int z);

 32 void ME()

 33 { int i,j;

 34     memset(flag,0,sizeof(flag));

 35     for(i=0; i<110; i++)

 36     {

 37         bin[i]=i;

 38         shen[i]=1;

 39     }

 40     for(i=0; i<110; i++)

 41     {

 42         for(j=0; j<110; j++)

 43         {

 44             mapp[i][j]=200;

 45         }

 46     }

 47 } void dis(int n,int k);

 48 int main(void)

 49 {

 50     int i,j,k,p,q,n;

 51     //freopen("data.in","r",stdin);

 52     //freopen("wrong.out","w",stdout);

 53     scanf("%d",&k);

 54     while(k--)

 55     {

 56         ME();scanf("%d",&n);

 57         int cnt=0;

 58         for(i=0; i<=n; i++)

 59         {

 60             scanf("%d %d",&bian[i].x,&bian[i].y);

 61             int s=cha(bian[i].x,bian[i].y);

 62             if(s==1)

 63             {

 64                 TWO[cnt++]=i;

 65             }

 66         }

 67         for(i=1; i<=n; i++)

 68         {

 69             for(j=i; bin[j]!=j;)

 70                 j=bin[j];

 71             HH[i]=j;

 72         }

 73         for(i=2; i<=n; i++)

 74         {

 75             if(HH[i]!=HH[1])

 76             {

 77                 break;

 78             }

 79         }

 80         if(i!=n+1)

 81         {

 82             printf("0\n");

 83         }

 84         else

 85         {

 86             int vx=bian[TWO[0]].x;

 87             int vy=bian[TWO[0]].y;

 88             int vxx=bian[TWO[1]].x;

 89             int vyy=bian[TWO[1]].y;

 90             for(i=0; i<=n; i++)

 91             {

 92                 if(i!=TWO[0]&&i!=TWO[1])

 93                 {

 94                     mapp[bian[i].x][bian[i].y]=1;

 95                     mapp[bian[i].y][bian[i].x]=1;

 96                     ma[bian[i].x][bian[i].y]=i;

 97                     ma[bian[i].y][bian[i].x]=i;

 98                 }

 99             }

100                 dis(vxx,n);

101                 int va=pre[vyy];int hh=vyy;

102                 memset(DD,0,sizeof(DD));

103                 while(va!=-1)

104                 {

105                     DD[va]=1;

106                     int xx=bian[va].x;

107                     int yy=bian[va].y;

108                     if(hh!=xx)

109                     {va=pre[xx];hh=xx;}

110                     else {va=pre[yy];hh=yy;}

111

112                 }

113             DD[TWO[1]]=1;

114                  dis(vx,n);

115                  va=pre[vy];hh=vy;

116                 memset(CC,0,sizeof(CC));

117                while(va!=-1)

118                 {

119                     CC[va]=1;

120                     int xx=bian[va].x;

121                     int yy=bian[va].y;

122                     if(hh!=xx)

123                     {va=pre[xx];hh=xx;}

124                     else {va=pre[yy];hh=yy;}

125

126                 }

127             CC[TWO[0]]=1;

128             int ans=0;int nk=0;int mk=0;

129             for(i=0;i<=n;i++)

130             {

131                 if(CC[i]&&DD[i])

132                 {

133                     ans++;

134                 }

135                 if(CC[i])

136                 {

137                     nk++;

138                 }

139                 if(DD[i])

140                 {

141                     mk++;

142                 }

143             }

144             int sum=nk+mk-ans+nk*mk-ans*ans;

145             printf("%d\n",sum);

146         }}return 0;    }

147    int cha(int x,int y)

148     {

149         int i,j;

150         int xx,yy;

151         for(xx=x; bin[xx]!=xx;)

152             xx=bin[xx];

153         for(yy=y; bin[yy]!=yy;)

154             yy=bin[yy];

155         if(xx==yy)

156         {

157             return 1;

158         }

159         if(xx!=yy)

160         {

161             if(shen[xx]>shen[yy])

162             {

163                 shen[xx]+=shen[yy];

164                 bin[yy]=xx;

165             }

166             else

167             {

168                 shen[yy]+=shen[xx];

169                 bin[xx]=yy;

170             }

171         }

172         return 0;

173     }

174     void dis(int n,int k)

175     {

176         fill(dj,dj+110,1000);

177         fill(pre,pre+110,-1);

178         dj[n]=0;int i,j;

179         memset(flag,0,sizeof(flag));

180         pre[n]=-1;

181         while(true)

182         {

183             int l=-1;

184             for(i=1; i<=k; i++)

185             {

186                 if((l==-1||(dj[l]>dj[i]))&&!flag[i])

187                 {

188                     l=i;

189                 }

190             }

191             if(l==-1)

192             {

193                 break;

194             }

195             flag[l]=true;

196             for(i=1; i<=k; i++)

197             {

198                 if(mapp[l][i]+dj[l]<dj[i])

199                 {

200                     pre[i]=ma[l][i];

201                     dj[i]=mapp[l][i]+dj[l];

202                 }

203             }

204         }

205     }

思路2：让 nn 个点联通最少需要 n-1n−1 条边，所以最多只能删除两条边，我们可以枚举删除的这两条边（或者唯一的一条边），然后并查集判断连通性就好了。时间复杂度 O(n^3)。

  1 #include<stdio.h>

  2 #include<algorithm>

  3 #include<iostream>

  4 #include<stdlib.h>

  5 #include<string.h>

  6 #include<math.h>

  7 #include<queue>

  8 #include<stack>

  9 #include<iomanip>

 10 #include<cstdio>

 11 #include<map>

 12 #include<set>

 13 #include <cmath>

 14 #include <ctime>

 15 #include <cstring>

 16 #include <cctype>

 17 #include <cassert>

 18 #include<vector>

 19 using namespace std;

 20 struct node

 21 {

 22     int x;

 23     int y;

 24 };

 25 node dian[200];

 26 vector<int>vec[102];

 27 bool flag[102];

 28 bool flag1[103];

 29 bool flag2[103];

 30 int bincha[102];

 31 int shendu[102];

 32 int huanyuan[102];

 33 int an=0;

 34 void me()

 35 {

 36     memset(flag1,0,sizeof(flag));

 37     memset(flag2,0,sizeof(flag1));

 38     memset(flag,0,sizeof(flag));

 39     int i,j;

 40     for(i=0; i<102; i++)

 41     {

 42         bincha[i]=i;

 43         shendu[i]=1;

 44     }

 45 }

 46 void BB(int a,int b)

 47 {

 48     int x,y;

 49     for(x=a; bincha[x]!=x;)

 50     {

 51         x=bincha[x];

 52     }

 53     for(y=b; bincha[y]!=y;)

 54     {

 55         y=bincha[y];

 56     }

 57     if(x!=y)

 58     {

 59         if(shendu[x]>shendu[y])

 60         {

 61             shendu[x]+=shendu[y];

 62             bincha[y]=x;

 63         }

 64         else

 65         {

 66             shendu[y]+=shendu[x];

 67             bincha[x]=y;

 68         }

 69     }

 70 }

 71 void slove (int s)

 72 {

 73     int i,j,k,m,n;

 74     int fl=0;int nn,mm;

 75     for(i=0; i<=s; i++)

 76     {

 77         for(j=i+1; j<=s; j++)

 78         {

 79             for(int z=0; z<102; z++)

 80             {

 81                 bincha[z]=z;

 82                 shendu[z]=1;

 83             }

 84             for(m=0; m<=s; m++)

 85             {

 86                 if(m!=i&&m!=j)

 87                 {

 88                     BB(dian[m].x,dian[m].y);

 89                 }

 90             }

 91             for(m=1;m<=s; m++)

 92             {

 93                 for(n=m; bincha[n]!=n;)

 94                     n=bincha[n];

 95                 huanyuan[m]=n;

 96             }

 97             for(n=2; n<=s; n++)

 98             {

 99                 if(huanyuan[n]!=huanyuan[1])

100                 {

101                     break;

102                 }

103             }

104             if(n==s+1)

105             {

106                 an++;

107                 flag[i]=true;

108                 flag[j]=true;

109

110             }

111         }

112         if(fl)

113             break;

114     }int ans[102];int cnt=0;

115     int bns[102];int cnt1=0;

116

117 }

118 int main(void)

119 {

120     int i,j,k,p,q;

121     int N;  //freopen("data.in","r",stdin);

122     //freopen("wrong.out","w",stdout);

123     cin>>k;

124     while(k--)

125     {  scanf("%d",&N) ;an=0;

126         for(i=0; i<102; i++)

127             vec[i].clear();

128         me();

129

130         for(i=0; i<N+1; i++)

131         {

132             cin>>p>>q;

133             dian[i].x=p;

134             dian[i].y=q;

135             vec[p].push_back(q);

136             vec[q].push_back(p);

137             BB(p,q);

138         }

139         for(i=1;i<=N;i++)

140         {

141             for(j=i;bincha[j]!=j;)

142                 j=bincha[j];

143             huanyuan[i]=j;

144         }

145         for(i=2;i<=N;i++)

146         {

147             if(huanyuan[i]!=huanyuan[1])

148             {

149                 break;

150             }

151         }

152         if(i!=N+1)

153         {

154             printf("0\n");

155         }

156         else

157         {

158             slove(N);

159             for(i=0;i<=N;i++)

160             {

161                 if(flag[i])

162                 {

163                     an++;

164                 }

165             }

166             printf("%d\n",an);

167         }

168

169     }

170     return 0;

171 }

N*N*N

 

最新文章

  1. ffmpeg - libavutil/attribute.h
  2. INNO setup安装卸载钱判断进程中是否在运行总结
  3. ECSHOP会员登录后直接进用户中心
  4. Android EventBus源码解析 带你深入理解EventBus
  5. nginx增加ssl服务方法
  6. 修改stb_image.c以让Duilib直接支持Ico格式的图标显示
  7. Linux 多学习过程
  8. MyBatis-plus 代码自动生成器
  9. django关闭调试信息，打开内置错误视图
  10. Python调用ansible API系列（一）获取资产信息
  11. 第八节，Opencv的基本使用------存取图像、视频功能、简单信息标注工具
  12. iptables和netfilter
  13. BZOJ3510 首都（LCT）
  14. MVC 实用构架实战（一）——项目结构搭建
  15. 001_fpm打包命令详解
  16. makefile 必知必会以及Makefile是怎样炼成的
  17. warning C4018: “&lt;”: 有符号/无符号不匹配
  18. React实战一
  19. Work at a KFC fast food restaurant
  20. 一点一点看JDK源码（〇）

热门文章

  1. javaWeb - 1 — servlet — 更新完毕
  2. Linux基础命令---enable开启shell命令
  3. MyBatis中sql实现时间查询的方法
  4. OpenStack之十： 安装dashboard
  5. 结合redis缓存的方式，查询和展示分类信息
  6. 远程调用RPC
  7. shell脚本 系统信息检测
  8. IO中同步异步，阻塞与非阻塞 -- 通俗篇
  9. 童鞋，[HttpClient发送文件] 的技术实践请查收
  10. [BUUCTF]PWN——mrctf2020_shellcode