首页 > 代码库 > hdu 4005 The war
hdu 4005 The war
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4005
In the war, the intelligence about the enemy is very important. Now, our troop has mastered the situation of the enemy‘s war zones, and known that these war zones can communicate to each other directly or indirectly through the network. We also know the enemy is going to build a new communication line to strengthen their communication network. Our task is to destroy their communication network, so that some of their war zones can‘t communicate. Each line has its "cost of destroy". If we want to destroy a line, we must spend the "cost of destroy" of this line. We want to finish this task using the least cost, but our enemy is very clever. Now, we know the network they have already built, but we know nothing about the new line which our enemy is going to build. In this condition, your task is to find the minimum cost that no matter where our enemy builds the new line, you can destroy it using the fixed money. Please give the minimum cost. For efficiency, we can only destroy one communication line.
题意：n个点m条边，无向图，每条边有一个值，如果我们删除这条边，我们需要花费的金额等同这条边上的值。最开始整个图是连通的，现在会加上一条未知的边进去形成新图，我们只能删除一条边，保证新图不连通，求需要的最小金额是多少。
解法：
无向图求连通分量。我们首先应该知道，因为加入的边未知，所以我们所求的最小金额就是无论加入的边在图中哪里，我们都可以删除一条边来使它不连通。so我们首先对图求解连通分量，然后缩点，形成一棵树。这时候，我们可以想到，在加入一条未知的边之后会形成一个环，显然最小值的边不是我们的答案，因为这条边有可能就在这个环中，这时候我们就删除不了边了（其他边的值都比这个值大）。
我们仔细想想可以发现：根据题意构造最优路径，一条路径通过以结点u为根的子树时，一定会经过以结点u为根的子树中边权最小的那条边，那么这时候我们除去这条路径后剩下的边权中的最小值就是我们要求的答案了。所以，我们的算法思想就是：递归求解每个结点为根的子树中的最小边和次小边，我们必须保证这里最小边和次小边不可能在一条路径上，然后求次小边中的最小值就是答案了。
总结：
连通分量的一道很好的题，想了一天也没有好的解法方法，最后看了别人的代码和讲解才有一些理解和感悟，特别是在保证最小边和次小边不能有机会在一条路径上的解决方法上很巧妙。
最后，有两个疑问一直想不通，现在还一直在苦想中。。。
1：图中有重边，这时候我们要么全部保留，要么留下一条边权最大或最小的。这道题，我们需要全部保留，但为什么不是只留下一条边？
2：这道题进行缩点的时候，我用low[]数组判断RE了，好像不是可以用low来判断是否在一个连通块中吗？
图论题做得少，努力补充过程中。。。。图论很有意思，加油！
贴上整个代码，一些调试的和多余的函数代码没有删除，仔细理解应该没问题。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<algorithm> 7 #include<vector> 8 #define inf 0x7fffffff 9 using namespace std; 10 const int maxn=10000+10; 11 const int M = 2e5+100; 12 int n,m; 13 struct Edge 14 { 15 int u,v,cost; 16 int next; 17 }edge[M]; 18 int head[maxn],edgenum; 19 void add(int u,int v,int cost) 20 { 21 Edge E={u,v,cost,head[u] }; 22 edge[edgenum]=E; 23 head[u]=edgenum++; 24 25 Edge E1={v,u,cost,head[v] }; 26 edge[edgenum]=E1; 27 head[v]=edgenum++; 28 } 29 30 int pre[maxn],low[maxn],dfs_clock,bcc_cnt,index; 31 int mark[maxn]; 32 vector< vector<Edge> > dfsmap; 33 vector<int> vec; 34 int color[maxn]; 35 int dfs(int u,int fa) 36 { 37 low[u]=pre[u]= ++dfs_clock; 38 int flag=1; 39 for (int i=head[u] ;i!=-1 ;i=edge[i].next) 40 { 41 int v=edge[i].v; 42 if (v==fa && flag) {flag=0;continue; } 43 if (!pre[v]) 44 { 45 dfs(v,u); 46 low[u]=min(low[u],low[v]); 47 } 48 else if (pre[v]<pre[u]) 49 low[u]=min(low[u],pre[v]); 50 } 51 } 52 void tarjan(int u,int fa){ 53 vec.push_back(u); 54 pre[u]=low[u]=index++; 55 mark[u]=true; 56 bool flag=true; 57 for(int i=head[u] ;i!=-1 ;i=edge[i].next){ 58 int d=edge[i].v; 59 if(d==fa && flag){flag=false;continue;} 60 if(!pre[d]){ 61 tarjan(d,u); 62 low[u]=min(low[u],low[d]); 63 }else { 64 low[u]=min(low[u],pre[d]); 65 } 66 } 67 if(low[u]==pre[u]){ 68 int d; 69 bcc_cnt++; 70 do{ 71 d=vec.back(); 72 vec.pop_back(); 73 color[d]=bcc_cnt; 74 mark[d]=false; 75 }while(d!=u); 76 } 77 } 78 void find_bcc() 79 { 80 memset(pre,0,sizeof(pre)); 81 memset(low,0,sizeof(low)); 82 memset(mark,false,sizeof(mark)); 83 vec.clear(); 84 dfs_clock=bcc_cnt=0; 85 index=1; 86 for (int i=1 ;i<=n ;i++) 87 if (!pre[i]) tarjan(i,-1); 88 } 89 int mindistance; 90 pair<int,int> dfs2(int u,int fa) 91 { 92 int first=inf,second=inf; 93 for (int i=0 ;i<dfsmap[u].size() ;i++) 94 { 95 int v=dfsmap[u][i].v; 96 int w=dfsmap[u][i].cost; 97 if (v==fa) continue; 98 pair<int,int> tmp=dfs2(v,u); 99 if (tmp.first>w) swap(tmp.first,w);100 //if (second>w) second=w;101 if (tmp.first<first)102 {103 second=min(tmp.second,first);104 first=tmp.first;105 }106 else if (tmp.first<second) second=tmp.first;107 }108 return make_pair(first,second);109 }110 int main()111 {112 int a,b,c;113 while (scanf("%d%d",&n,&m)!=EOF)114 {115 memset(head,-1,sizeof(head));116 edgenum=0;117 for (int i=0 ;i<m ;i++)118 {119 scanf("%d%d%d",&a,&b,&c);120 add(a,b,c);121 }122 find_bcc();123 cout<<endl<<bcc_cnt<<endl;124 for (int i=1 ;i<=n ;i++)125 cout<<i<<" "<<low[i]<<" "<<color[i]<<endl;126 cout<<endl;127 dfsmap.resize(n+10);128 for (int i=1 ;i<n+10 ;i++) dfsmap[i].clear();129 int mindist=inf,uu=0,vv=0;130 for (int i=0 ;i<edgenum ;i++)131 {132 int u=edge[i].u;133 int v=edge[i].v;134 int w=edge[i].cost;135 int u1=color[u] ,v1=color[v] ;136 if (u1 != v1)137 {138 Edge E={u1,v1,edge[i].cost };139 dfsmap[u1].push_back(E);140 if (edge[i].cost<mindist)141 {142 mindist=edge[i].cost;143 uu=u1 ;vv=v1 ;144 }145 }146 }147 // for (int i=1 ;i<=n ;i++)148 // {149 // int u=low[i];150 // for (int j=head[i] ;j!=-1 ;j=edge[j].next)151 // {152 // int v=low[edge[j].v ];153 // if (u!=v)154 // {155 // Edge E={u,v,edge[j].cost };156 // dfsmap[u].push_back(E);157 // if (edge[j].cost<mindist)158 // {159 // mindist=edge[j].cost;160 // uu=u ;vv=v ;161 // }162 // }163 // }164 // }165 mindistance=inf;166 pair<int,int> p1=dfs2(uu,vv);167 pair<int,int> p2=dfs2(vv,uu);168 //pair<int,int> p1=dfs3(uu,vv);169 //pair<int,int> p2=dfs3(vv,uu);170 mindistance=min(mindistance,min(p1.second,p2.second));171 printf("%d\n",mindistance==inf ? -1 : mindistance);172 }173 return 0;174 }
后续：感谢大牛提出宝贵的意见。。。。
hdu 4005 The war
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。