乍一看一个模板题，仔细一看还是模板题，但是三个坑。1，不是连通图，放0个。2 守卫为0，放1个。 3注意重边。
#include<iostream> #include<cstdio> #include<vector> #include<queue> #include<algorithm> #include<stack> #include<cstring> using namespace std; #define maxn 1005 int head[maxn],dfn[maxn],low[maxn],guard[maxn][maxn],tot,n; int vis[maxn],all,index,bri[maxn*maxn]; struct Edge { int to,nxt,g; } edge[maxn*maxn*2]; queue<int> que; void bfs(int u) { vis[u] = 1; que.push(u); while(!que.empty()) { int now = que.front(); que.pop(); for(int i = head[now]; i != -1; i = edge[i].nxt) { int v = edge[i].to; if(!vis[v]) {que.push(v);vis[v] = 1;} } } } bool judge() { memset(vis,0,sizeof(vis)); int sum = 0; while(!que.empty()) que.pop(); for(int i = 1; i <= n; i++) { if(!vis[i]) { sum++; bfs(i); } } if(sum==1) return true; return false; } void addedge(int u,int v,int w) { edge[tot].to = v; edge[tot].g = w; edge[tot].nxt = head[u]; head[u] = tot++; } void init() { all = index = 0; memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); } void tarjan(int u,int fa) { low[u] = dfn[u] = ++index; for(int i = head[u];i != -1;i = edge[i].nxt){ int v = edge[i].to; if(!dfn[v]){ tarjan(v,u); low[u] = min(low[u],low[v]); if(low[v] > dfn[u] && guard[u][v]!=-2&&guard[v][u]!=-2){ bri[all++] = edge[i].g; } } else if(v != fa) low[u] = min(low[u],dfn[v]); } } int main() { int m,a,b,w; while(~scanf("%d%d",&n,&m)) { if(n+m == 0) break; memset(head,-1,sizeof(head)); tot = 0; memset(guard,-1,sizeof(guard)); for(int i = 0; i < m; i++) { scanf("%d%d%d",&a,&b,&w); if(guard[a][b]==-1 && guard[b][a]==-1) { addedge(a,b,w); addedge(b,a,w); guard[a][b] = guard[b][a] = w; } else { guard[a][b] = guard[b][a] = -2; } } if(!judge()) { puts("0"); continue; } init(); tarjan(1,-1); if(all == 0){ puts("-1"); continue; } sort(bri,bri+all); if(bri[0] == 0) puts("1"); else printf("%d ",bri[0]); } }