Playing on Graph

Time Limit: 20 Sec  Memory Limit: 512 MB

Description

　　

Input

　　

Output

　　

Sample Input

　　5 4

　　1 2

　　2 3

　　3 4

　　3 5

Sample Output

　　3

HINT

　　n <= 1000, m <= 10^5

Solution

　　我们先考虑无解的情况。显然就是图中有奇环的时候无解，因为你将奇环上两点缩起来，最后必定会变成一个三元环，而三元环是不能合并的。所以就可以Dfs黑白染色一下，若是搜到两个同色的话即是有奇环。

　　我们再考虑如何构造一种方案，显然，我们先找出一个点root，然后将所有 dist 相同的并起来，这样是一组可行解。可以发现，所有的方案都可以由这种方式构造出来。

　　那么这时候，确定一点　　为 root 的时候，贡献显然等于最大的 dist。那么我们将所有点都确定为root一遍，然后Bfs求一下dist，取出最大dist，就可以得到一个联通块的答案了。

　　显然可以有多个连通块，Ans = Σ每个连通块的答案。

Code

1 #include
      
          2 #include
       
           3 #include
        
            4 #include
         
             5 #include
          
              6 #include
           
             7 #include
            
              8 using namespace std; 9 typedef long long s64;10 11 const int ONE = 800005;12 const int Base = 2005;13 14 int n, m;15 int x, y;16 int next[ONE], first[ONE], go[ONE], tot;17 int vis[ONE], col[ONE];18 int pd;19 int vis_a[ONE], record[ONE], num, dist[ONE];20 int Ans;21 queue 
             
               q;22 23 int get()24 { 25 int res;char c; 26 while( (c=getchar())<48 || c>57 );27 res=c-48; 28 while( (c=getchar())>=48 && c<=57 ) 29 res=res*10+c-48; 30 return res; 31 } 32 33 void Add(int u, int v)34 {35 next[++tot] = first[u], first[u] = tot, go[tot] = v;36 next[++tot] = first[v], first[v] = tot, go[tot] = u;37 }38 39 void Dfs(int u, int color)40 {41 vis[u] = 1;42 col[u] = color;43 record[++num] = u;44 for(int e = first[u]; e; e = next[e])45 {46 int v = go[e];47 if(!vis[v]) Dfs(v, color ^ 1);48 else pd |= col[v] == col[u];49 }50 }51 52 int Bfs(int S)53 {54 for(int i = 1; i <= n; i++) dist[i] = vis_a[i] = 0;55 dist[S] = 0, vis_a[S] = 1, q.push(S);56 while(!q.empty())57 {58 int u = q.front(); q.pop();59 for(int e = first[u]; e; e = next[e])60 {61 int v = go[e];62 if(vis_a[v]) continue;63 vis_a[v] = 1;64 dist[v] = dist[u] + 1;65 q.push(v);66 }67 }68 69 int res = 0;70 for(int i = 1; i <= n; i++)71 res = max(res, dist[i]);72 return res;73 }74 75 int main()76 {77 n = get(); m = get();78 for(int i = 1; i <= m; i++)79 {80 x = get(), y = get();81 Add(x, y);82 }83 84 for(int i = 1; i <= n; i++)85 if(!vis[i])86 {87 num = 0;88 Dfs(i, 0);89 if(pd == 1) {printf("-1"); return 0;}90 91 int res = 0;92 for(int j = 1; j <= num; j++)93 res = max(res, Bfs(record[j]));94 Ans += res;95 }96 97 printf("%d", Ans);98 }
             
            
           
          
         
        
       
      

 

un[ʌn]

---

• n. (Un)人名；(柬)温
• pron. 家伙，东西