51nod 1444 破坏道路（最短路）

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1444

题意：

思路：

哇，思路爆炸。

因为每条边的权值都为1，所以可以直接用bfs来求出任意两个点之间的最短距离，复杂度为$O(n^2)$。

然后之后再暴力枚举一下，看看这两条路径之间是否会有重复的边。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<vector>
 6 #include<stack>
 7 #include<queue>
 8 #include<cmath>
 9 #include<map>
10 #include<set>
11 using namespace std;
12 typedef long long ll;
13 const int INF = 0x3f3f3f3f;
14 const int maxn=3500+5;
15 
16 int n, m;
17 vector<int> G[maxn];
18 int vis[maxn];
19 int d[maxn][maxn];
20 int s1,t1,l1,s2,t2,l2;
21 
22 
23 void bfs()
24 {
25    // memset(d,0,sizeof(d));
26     for(int i=1;i<=n;i++)
27     {
28         memset(vis,0,sizeof(vis));
29         queue<int> Q;
30         Q.push(i);
31         vis[i]=1;
32         while(!Q.empty())
33         {
34             int u=Q.front(); Q.pop();
35             for(int j=0;j<G[u].size();j++)
36             {
37                 int v=G[u][j];
38                 if(!vis[v])
39                 {
40                     vis[v]=1;
41                     d[i][v]=d[i][u]+1;
42                     Q.push(v);
43                 }
44             }
45         }
46     }
47 }
48 
49 
50 bool judge(int s1, int t1, int s2, int t2, int i, int j)
51 {
52     return d[s1][i] + d[i][j] + d[j][t1] <= l1 && d[s2][i] + d[i][j] + d[j][t2] <= l2;
53 }
54 
55 int main()
56 {
57     //freopen("in.txt","r",stdin);
58     scanf("%d%d",&n,&m);
59     for(int i=1;i<=m;i++)
60     {
61         int u,v;
62         scanf("%d%d",&u,&v);
63         G[u].push_back(v);
64         G[v].push_back(u);
65     }
66 
67     scanf("%d%d%d",&s1,&t1,&l1);
68     scanf("%d%d%d",&s2,&t2,&l2);
69 
70     bfs();
71 
72     int ans=d[s1][t1]+d[s2][t2];
73     if(d[s1][t1]>l1 || d[s2][t2]>l2)  puts("-1");
74     else
75     {
76         for(int i=1;i<=n;i++)
77         for(int j=1;j<=n;j++)
78         {
79           if (judge(s1, t1, s2, t2, i, j))
80             {
81                 ans = min(ans, d[s1][i] + d[i][j] + d[j][t1] + d[s2][i] + d[j][t2]);
82             }
83             if (judge(t1, s1, t2, s2, i, j))
84             {
85                 ans = min(ans, d[t1][i] + d[i][j] + d[j][s1] + d[t2][i] + d[j][s2]);
86             }
87             if (judge(s1, t1, t2, s2, i, j))
88             {
89                 ans = min(ans, d[s1][i] + d[i][j] + d[j][t1] + d[t2][i] + d[j][s2]);
90             }
91             if (judge(t1, s1, s2, t2, i, j))
92             {
93                 ans = min(ans, d[t1][i] + d[i][j] + d[j][s1] + d[s2][i] + d[j][t2]);
94             }
95         }
96         printf("%d
",m-ans);
97     }
98     return 0;
99 }