题目链接: hdu 4738
题目大意: 曹操有N个岛,这些岛用M座桥连接起来
每座桥有士兵把守(也可能没有)
周瑜想让这N个岛不连通,但只能炸掉一座桥
并且炸掉一座桥需要派出不小于守桥士兵数的人去
解题思路: 首先判断图是否连通,不连通则不需要去炸桥,输出0
图连通,则可以用Tarjan找割边
割边不存在输出-1表示不能达到目的
找到所有的割边,只需要炸掉其中守兵数最少的桥即可
PS: 桥的守兵数为0时,也需要派出一个人去炸桥!
代码:
#pragma comment(linker, "/STACK:1024000000,1024000000") #include <stdio.h> #include <string.h> #include <stdlib.h> #include <algorithm> using namespace std; #define MAX 11000 #define MIN(a,b) a<b?a:b struct snode{ int to,next,w; }Roads[3000000]; int Index,n,pre[MAX],dnf[MAX],low[MAX],visit[MAX],high,mm,flag,edge[2100][2100],ans[MAX*50],ansn; void Add_edge(int a,int b,int w1) { Roads[Index].to=b; Roads[Index].next=pre[a]; Roads[Index].w=w1; pre[a]=Index++; } void DFS(int u) //判断图是否联通 { int vv,v; visit[u]=1; mm++; for(vv=pre[u];vv!=-1;vv=Roads[vv].next) { v=Roads[vv].to; if(!visit[v]) DFS(v); } } void Tarjan(int u,int father) //Tarjan搜索桥 { int v,vv; for(v=pre[u];v!=-1;v=Roads[v].next) { vv=Roads[v].to; if(!visit[vv]) { low[vv]=dnf[vv]=++high; visit[vv]=1; Tarjan(vv,u); low[u]=MIN(low[u],low[vv]); if(low[vv]>dnf[u]&&edge[vv][u]==1) //没有重边 { ans[ansn++]=Roads[v].w; } } else if(vv!=father) { low[u]=MIN(low[u],dnf[vv]); } } } int main() { int a,b,c,m,i; while(scanf("%d%d",&n,&m)) { if(n==0&&m==0) break; ansn=0; memset(visit,0,sizeof(visit)); memset(edge,0,sizeof(edge)); memset(pre,-1,sizeof(pre)); Index=0; for(i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&c); Add_edge(a,b,c); Add_edge(b,a,c); edge[a][b]++; edge[b][a]++; } flag=0; mm=0; DFS(1); if(mm<n) //如果不联通,则输出0,因为不用去炸已经达到目的了 { flag=1; printf("0\n"); continue; } memset(visit,0,sizeof(visit)); dnf[1]=low[1]=visit[1]=high=1; //初始化 Tarjan(1,-1); if(ansn>=1) { sort(ans,ans+ansn); //按照付出的代价从小到达输出 if(ans[0]==0) //***如果那座桥没人把守,至少需要派一个兵去炸 printf("1\n"); else printf("%d\n",ans[0]); continue; } else //不能达到目的 { printf("-1\n"); continue; } } return 0; }