hdu--4118--continue??

首页 > 代码库 > hdu--4118--continue??

2024-07-31 21:40:36 217人阅读

这题用了我大概一天的时间断断续续来想它吧我就无语了太白痴了 F M L

这边有一个很重要的条件就是N个点只有N-1条的边而且这是个无向连通的其实这边不应该用连通来描述因为它是用来形容图的而这题的结构是个树因为不会形成闭合回路

将这么一大串的英文单词转换下就是说使这N个点各自选择一条路线到达一个终点而且每个人都不能留在原地和终点是相同的地方

这题你要是用局部来考虑就很麻烦了要全局来看 -- 因为我们最终要得到的结果是路线距离总和是最大的

那么为了达到最大就是说任意一条边我们应该尽量走最大的次数 --- 那么怎么考虑这个最大呢？

我们可以这样看

对于连接A-B的边而言它的左右端点A B各自所在的集合数分别是2 和 3 那么最多就是A E 2个顶点与B所在的集合中的2个顶点进行交换位置那么这样就会在A-B这条边上走过的距离为 2*min(S(A),S(B)) * Len(A-B)

这就是这题的想法了

然后就去实现了.. 用dfs会爆栈那就考虑用非递归的方法来实现

其实因为dfs利用的是系统栈来实现递归那么非递归自然是我们模拟一个stack 我这边就直接用stl中的stack了当然从效率上来说肯定直接数组模拟stack会更快的

首先任意选取一个点遍历与它相连的所有边你可以当成将该点看成树的root 无所谓的... 一般我们选顶点编号1 看上去舒服点

然后就是首先一直向下遍历到叶子结点为止就向上回溯这边注意flag变量的使用是精髓如果没有continue就标志该点是叶子结点了可以向上回溯了 --我觉得这题的代码在以后都会有很大价值~~

  1 #include <iostream>  2 #include <cstring>  3 #include <algorithm>  4 #include <stack>  5 using namespace std;  6   7 typedef long long LL;  8 LL ans;  9 const int size = 100010; 10 int cnt; 11 int n; 12 struct graph 13 { 14     int to; 15     int from; 16     LL len; 17     int next; 18 }edge[size*2]; 19 int head[size]; 20 int num[size]; 21 bool vis[size]; 22 stack<int>s; 23  24 void init( ) 25 { 26     while(!s.empty()) 27         s.pop(); 28     memset( head , -1 , sizeof(head) ); 29     memset( vis , false , sizeof(vis) ); 30     memset( num , 0 , sizeof(num) ); 31 } 32  33 void addEdge( int from , int to , LL len ) 34 { 35     edge[cnt].from = from; 36     edge[cnt].to = to; 37     edge[cnt].len = len; 38     edge[cnt].next = head[from]; 39     head[from] = cnt ++; 40 } 41  42 void solve( int x ) 43 { 44     int u , v; 45     bool flag; 46     s.push( x ); 47     vis[x] = true; 48     while( !s.empty() ) 49     { 50         u = s.top(); 51         flag = false; 52         for(  int i = head[u] ; ~i ; i=edge[i].next ) 53         { 54             v = edge[i].to; 55             if( !vis[v] ) 56             { 57                 s.push( v ); 58                 vis[v] = true; 59                 flag = true; 60             } 61         } 62         if( flag ) 63             continue; 64         s.pop(); 65         for( int i = head[u] ; ~i ; i = edge[i].next ) 66         { 67             v = edge[i].to; 68             if( num[v]!=0 ) 69             { 70                 num[u] += num[v]; 71                 ans += 2 * edge[i].len * min( num[v] , n-num[v] ); 72             } 73         } 74         num[u] ++; 75     } 76 } 77  78 int main() 79 { 80     cin.sync_with_stdio(false); 81     int t , x , y; 82     LL z; 83     cin >> t; 84     for( int k = 1 ; k<=t ; k++ ) 85     { 86         cnt = 0; 87         ans = 0; 88         cin >> n; 89         init(); 90         for( int i = 1 ; i<=n-1 ; i++ ) 91         { 92             cin >> x >> y >> z; 93             addEdge( x , y , z ); 94             addEdge( y , x , z ); 95         } 96         solve( 1 ); 97         cout << "Case " << "#" << k << ": " << ans << endl; 98     } 99     return 0;100 }

View Code