Caocao's Bridges

 

题意：一个带权无向图，破坏一条边的代价是权重，如果可以破坏一条边使得存在两点不能互达，输出最小代价。

 【找权值最小的桥】

找到桥更新答案即可。

注意如果本身图就不连通，则不需要破坏，代价为0

如果图不存在桥，则不满足输出-1

如果最后求出代价为0，则要输出1（因为题意是破坏桥，即使没有人守卫也要派一个人去炸桥）

1 #include 
      
        2 using namespace std; 3 const int inf=0x3f3f3f3f; 4 const int maxv=1000; 5 int n,m; 6 int ans; 7 struct Edge 8 { 9     int v,w,nex;10 }e[maxv*maxv<<1];11 int head[maxv];12 int cnt=0;13 void init()14 {15     memset(head,-1,sizeof(head));16     cnt=0;17 18     ans=inf;19 }20 void add(int u,int v,int w)21 {22     e[cnt].v=v;23     e[cnt].w=w;24     e[cnt].nex=head[u];25     head[u]=cnt++;26 }27 28 int pre[maxv],low[maxv],dfsk,bct;29 30 void Tarjin(int u,int id)31 {32     pre[u]=low[u]=++dfsk;33     for(int i=head[u];i!=-1;i=e[i].nex)34     {35         int v=e[i].v;36         if(i==(id^1)) continue;  //反向边37         if(!pre[v])38         {39             Tarjin(v,i);40             low[u]=min(low[u],low[v]);41             if(low[v]>pre[u]&&ans>e[i].w) ans=e[i].w;42         }43         else low[u]=min(low[u],pre[v]);44     }45 }46 47 int main()48 {49     while(scanf("%d%d",&n,&m)&&(n||m))50     {51         init();52         int u,v,w;53         for(int i=0;i
       
        1) ans=0;66         else if(ans==inf) ans=-1;67         else if(ans==0) ans=1;68         printf("%d\n",ans);69 70 71     }72 73 }
       
      

 不用low数组，用dfs返回low值慢一些

1 #include 
      
        2 using namespace std; 3 const int inf=0x3f3f3f3f; 4 const int maxv=1000; 5 int n,m; 6 int ans; 7 struct Edge 8 { 9     int v,w,nex;10 }e[maxv*maxv<<1];11 int head[maxv];12 int cnt=0;13 void init()14 {15     memset(head,-1,sizeof(head));16     cnt=0;17 18     ans=inf;19 }20 void add(int u,int v,int w)21 {22     e[cnt].v=v;23     e[cnt].w=w;24     e[cnt].nex=head[u];25     head[u]=cnt++;26 }27 28 int pre[maxv],dfsk,bct;29 30 int Tarjin(int u,int id)31 {32     int lowu=pre[u]=++dfsk;33     for(int i=head[u];i!=-1;i=e[i].nex)34     {35         int v=e[i].v;36         if(i==(id^1)) continue;  //反向边37         if(!pre[v])38         {39             int lowv=Tarjin(v,i);40             lowu=min(lowu,lowv);41             if(lowv>pre[u]&&ans>e[i].w) ans=e[i].w;42         }43         else lowu=min(lowu,pre[v]);44     }45     return lowu;46 }47 48 int main()49 {50     while(scanf("%d%d",&n,&m)&&(n||m))51     {52         init();53         int u,v,w;54         for(int i=0;i
       
        1) ans=0;66         else if(ans==inf) ans=-1;67         else if(ans==0) ans=1;68         printf("%d\n",ans);69     }70 }