青色系网站/郑州关键词优化费用

题意：

       现在有个(可重边)无向图，无向图的每条边上都有一定数目的守卫，你现在想派人去炸掉这个图的一条边，是的该图不连通。但是你只能炸1条边且如果该边守卫为x人，那么你至少要派x个人过去。所以现在问你最少需要派多少人出发？

思路：就是求一个有重边的无向图的桥，有几个比较坑的地方

            1，所给的图可能不连通，且不连通的时候不需要炸，输出0

            2，当所要去炸的桥上的守卫数=0时，需要输出1而不是0

            3，有重边

            我的思路很简单，如果有重边的话那么就一定不是桥，那么只需要给一个特别一点值，在dfs里面更新的时候判断如果是这个特别的值就可以跳过了。

这个不能像求联通块那样 直接 !k continue就好了， 因为求割边是 在!dfn时候做的。。含重边求桥两种方法把

#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <map>
#include <algorithm>
using namespace std;
const int maxn = 1e3 + 5;
const int INF = 1e9;
int n, m,low[maxn], dfn[maxn], id[maxn], scc_cnt, dfs_cnt, cnt;
int g[maxn][maxn], ans, d[maxn][maxn];
vector<int> v[maxn];
map<int, int> mp;
void init()
{memset(low, 0, sizeof(low));memset(id, 0, sizeof(id));memset(dfn, 0, sizeof(dfn));scc_cnt = dfs_cnt = cnt = 0;for(int i = 0; i < maxn; i++)v[i].clear();memset(g, 0, sizeof(g));
}
void tarjan(int x, int f)
{dfn[x] = low[x] = ++dfs_cnt;int k = 0;for(int i = 0; i < v[x].size(); i++){int to = v[x][i];if(to == f && !k){k++;continue;}if(!dfn[to]){tarjan(to, x);low[x] = min(low[x], low[to]);if(low[to] > dfn[x] && g[x][to] != -1)ans = min(ans, g[x][to]), cnt++;}else if(dfn[to] < dfn[x])low[x] = min(low[x], dfn[to]);}
}
int main()
{
//    freopen("in.txt", "r", stdin);while(~scanf("%d%d",&n, &m), n+m){init();int x, y, z;for(int i = 1; i <= m; i++){scanf("%d%d%d", &x, &y, &z);if(!g[x][y]){v[x].push_back(y);v[y].push_back(x);g[x][y] = z;g[y][x] = z;}else{g[x][y] = -1;g[y][x] = -1;}}ans = INF;cnt = 0;tarjan(1, -1);
//        cout << cnt << endl;int flag = 0;for(int i = 1; i <= n; i++)if(!dfn[i]){flag = 1;break;}if(ans == 0)puts("1");else if(flag)puts("0");else if(ans == INF)puts("-1");elseprintf("%d\n", ans);}return 0;
}

    本题的本质还是无向图求桥，且求得是守卫数目最少的那个桥。但是本题有3个点要注意:

       1.所给的图可能不连通,且不连通的时候不需要炸,输出0.

       2.当所要去炸的桥上的守卫数=0时,我们需要派的人数是1不是0.

       3.任意两个节点u与v之间可能存在多条边。

       对于上面的1与2点,我们在原始tarjan()函数运行完后加一些判断就能解决.

       不过对于重边无向图,首先我们要用邻接表来保存图了(不能再用vector的邻接矩阵了).

       然后之前无重边的时候我们都是用过fa来标记父节点的，如果u的儿子等于fa，那么直接跳过。即如果u不通过儿子连回fa的话，low[u]==pre[u]肯定>pre[fa]。现在本题其实u是可以通过另一条(fa,u)的边连回fa的，所以这里即使u不通过儿子连回fa的话，low[u]==也可以==pre[fa]。因为fa通过边1到u，u可以通过边2到fa。

       所以本题把无向图转换成有向图来做：

       把每条无向边分为两条有向边i与i+1,如果u通过边i到达了v,那么v中必然有一条边是i^1且可以通过该i^1边到u.所以如果在v节点遍历时到达i^1边时,我们直接跳过.

       具体实现还是需要体会代码才能清晰.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000+10;
const int maxm=2*1000*1000+100;
int n,m;
int tot;
int head[maxn];
struct Edge
{int to,next,w;
}edges[maxm];
void add_edge(int u,int v,int w)
{edges[tot]=(Edge){v,head[u],w};head[u]=tot++;edges[tot]=(Edge){u,head[v],w};head[v]=tot++;
}int pre[maxn],low[maxn];
int dfs_clock,point_num;
int ans;
void tarjan(int u,int E)
{low[u]=pre[u]=++dfs_clock;for(int e=head[u];e!=-1;e=edges[e].next){int v=edges[e].to;if(e==(E^1)) continue;if(!pre[v]){tarjan(v,e);low[u]=min(low[u],low[v]);if(low[v]>pre[u])ans=min(ans,edges[e].w);}else low[u]=min(low[u],pre[v]);}point_num++;
}
int main()
{while(scanf("%d%d",&n,&m)==2&&n){ans=1000000;dfs_clock=point_num=tot=0;memset(pre,0,sizeof(pre));memset(head,-1,sizeof(head));for(int i=0;i<m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);add_edge(u,v,w);}tarjan(1,-1);if(point_num<n) printf("0\n");          //图不连通,不用炸else if(ans==1000000) printf("-1\n");   //图中无桥else if(ans==0) printf("%d\n",1);       //桥上兵为0else printf("%d\n",ans);}return 0;
}

/* ***********************************************
Author        :kuangbin
Created Time  :2013/9/15 星期日 12:11:49
File Name     :2013杭州网络赛\1001.cpp
************************************************ */#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int INF = 0x3f3f3f3f;
/*
*  求 无向图的割点和桥
*  可以找出割点和桥，求删掉每个点后增加的连通块。
*  需要注意重边的处理，可以先用矩阵存，再转邻接表，或者进行判重
*/
const int MAXN = 10010;
const int MAXM = 2000010;
struct Edge
{int to,next;int w;bool cut;//是否为桥的标记
}edge[MAXM];
int head[MAXN],tot;
int Low[MAXN],DFN[MAXN],Stack[MAXN];
int Index,top;
bool Instack[MAXN];
bool cut[MAXN];
int add_block[MAXN];//删除一个点后增加的连通块
int bridge;void addedge(int u,int v,int w)
{edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut = false;edge[tot].w = w;head[u] = tot++;
}void Tarjan(int u,int pre)
{int v;Low[u] = DFN[u] = ++Index;Stack[top++] = u;Instack[u] = true;int son = 0;int pre_num = 0;for(int i = head[u];i != -1;i = edge[i].next){v = edge[i].to;if(v == pre && pre_num == 0){pre_num++;continue;}if( !DFN[v] ){son++;Tarjan(v,u);if(Low[u] > Low[v])Low[u] = Low[v];//桥//一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)<Low(v)。if(Low[v] > DFN[u]){bridge++;edge[i].cut = true;edge[i^1].cut = true;}//割点//一个顶点u是割点，当且仅当满足(1)或(2) (1) u为树根，且u有多于一个子树。//(2) u不为树根，且满足存在(u,v)为树枝边(或称父子边，//即u为v在搜索树中的父亲)，使得DFS(u)<=Low(v)if(u != pre && Low[v] >= DFN[u])//不是树根{cut[u] = true;add_block[u]++;}}else if( Low[u] > DFN[v])Low[u] = DFN[v];}//树根，分支数大于1if(u == pre && son > 1)cut[u] = true;if(u == pre)add_block[u] = son - 1;Instack[u] = false;top--;
}
int  solve(int N)
{memset(DFN,0,sizeof(DFN));memset(Instack,false,sizeof(Instack));memset(add_block,0,sizeof(add_block));memset(cut,false,sizeof(cut));Index = top = 0;bridge = 0;for(int i = 1;i <= N;i++)if( !DFN[i] )Tarjan(i,i);int ret = INF;for(int u = 1; u <= N;u++)for(int i = head[u]; i != -1;i = edge[i].next)if(edge[i].cut)ret = min(ret,edge[i].w);if(ret == INF)ret = -1;if(ret == 0)ret++;return ret;
}
int F[MAXN];
int find(int x)
{if(F[x] == -1)return x;else return F[x] = find(F[x]);
}
void init()
{memset(F,-1,sizeof(F));tot = 0;memset(head,-1,sizeof(head));
}
void bing(int u,int v)
{int t1 = find(u);int t2 = find(v);if(t1 != t2)F[t1] = t2;
}
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int n,m;while(scanf("%d%d",&n,&m) == 2){if(n == 0 && m == 0)break;int u,v,w;init();while(m--){scanf("%d%d%d",&u,&v,&w);if(u == v)continue;addedge(u,v,w);addedge(v,u,w);bing(u,v);}bool flag = true;for(int i = 1; i <= n;i++)if(find(i) != find(1))flag = false;if(!flag){printf("0\n");continue;}printf("%d\n",solve(n));}return 0;
}