题目链接: hdu 4738
题目大意: 曹操有N个岛，这些岛用M座桥连接起来
每座桥有士兵把守(也可能没有)
周瑜想让这N个岛不连通，但只能炸掉一座桥
并且炸掉一座桥需要派出不小于守桥士兵数的人去
解题思路: 首先判断图是否连通，不连通则不需要去炸桥，输出0
图连通，则可以用Tarjan找割边
割边不存在输出-1表示不能达到目的
找到所有的割边，只需要炸掉其中守兵数最少的桥即可
PS: 桥的守兵数为0时，也需要派出一个人去炸桥！
求桥的第一种写法：
#include"string.h" #include"stdio.h" #include"algorithm" #include"iostream" #include"stack" #define M 1111 #define inf 999999999 using namespace std; struct st { int u,v,w,next; }edge[M*M*2]; int head[M],dfn[M],low[M],n,t,index,num; int use[M],belong[M]; void init() { t=0; memset(head,-1,sizeof(head)); } void add(int u,int v,int w) { edge[t].u=u; edge[t].v=v; edge[t].w=w; edge[t].next=head[u]; head[u]=t++; } stack<int>q; void tarjan(int u,int id) { dfn[u]=low[u]=++index; q.push(u); use[u]=1; for(int i=head[u];i!=-1;i=edge[i].next) { if(i==(1^id))continue; int v=edge[i].v; if(!dfn[v]) { tarjan(v,i); low[u]=min(low[u],low[v]); } else if(use[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { num++; int v; do { v=q.top(); q.pop(); use[v]=0; belong[v]=num; }while(u!=v); } } int solve() { index=num=0; int ans=0; memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); for(int i=1;i<=n;i++) { if(!dfn[i]) { ans++; tarjan(i,-1); } } return ans; } int main() { int m; while(scanf("%d%d",&n,&m),m||n) { init(); while(m--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,c); } int msg=solve(); int mini=inf; for(int i=0;i<t;i+=2) { int u=edge[i].u; int v=edge[i].v; if(belong[u]!=belong[v]) mini=min(mini,edge[i].w); } if(msg>1) printf("0 "); else if(mini>=inf) printf("-1 "); else { if(mini==0) printf("1 "); else printf("%d ",mini); } } }
求桥的第二种写法：
#include"string.h" #include"stdio.h" #include"iostream" #define M 1111 #define inf 999999999 using namespace std; struct st { int u,v,w,next; }edge[M*M*2]; int head[M],dfn[M],low[M],bridge[M],n,t,index,num,mini,flag; void init() { t=0; memset(head,-1,sizeof(head)); } void add(int u,int v,int w) { edge[t].u=u; edge[t].v=v; edge[t].w=w; edge[t].next=head[u]; head[u]=t++; } void tarjan(int u,int id) { dfn[u]=low[u]=++index; int i; for(i=head[u];i!=-1;i=edge[i].next) { if(i==(1^id))continue; int v=edge[i].v; if(!dfn[v]) { tarjan(v,i); low[u]=min(low[u],low[v]); if(low[v]>dfn[u]) { bridge[num++]=i; if(mini>edge[i].w) mini=edge[i].w; } } low[u]=min(low[u],dfn[v]); } } void solve() { index=num=flag=0; memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); for(int i=1;i<=n;i++) { if(!dfn[i]) { flag++; tarjan(i,-1); } } } int main() { int m; while(scanf("%d%d",&n,&m),m||n) { init(); while(m--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); add(b,a,c); } mini=inf; solve(); if(flag>1) printf("0 "); else if(num==0) printf("-1 "); else { if(mini==0) printf("1 "); else printf("%d ",mini); } } }
题目链接：hdu3849
题目大意：给出一些字符串网络联通图，问有多少个关键路径破坏后使图不连通，若图本身不连通的时候就直接输出0
程序：
#include"string.h" #include"stdio.h" #include"iostream" #include"stdlib.h" #define M 10009 #define inf 999999999 #include"map" #include"string" using namespace std; int cmp(const void *a,const void *b) { return *(int*)a-*(int*)b; } struct st { int u,v,next; }edge[M*30]; int head[M],dfn[M],low[M],bridge[M],n,t,index,num,flag; char mp1[M][33]; void init() { t=0; memset(head,-1,sizeof(head)); } void add(int u,int v) { edge[t].u=u; edge[t].v=v; edge[t].next=head[u]; head[u]=t++; } void tarjan(int u,int id) { dfn[u]=low[u]=++index; int i; for(i=head[u];i!=-1;i=edge[i].next) { if(i==(1^id))continue; int v=edge[i].v; if(!dfn[v]) { tarjan(v,i); low[u]=min(low[u],low[v]); if(low[v]>dfn[u]) bridge[num++]=i; } low[u]=min(low[u],dfn[v]); } } void solve() { index=num=flag=0; memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); for(int i=1;i<=n;i++) { if(!dfn[i]) { flag++; tarjan(i,-1); } } } int main() { int T,m,i; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); int k=1; init(); map<string,int>mp; while(m--) { char ch1[33],ch2[33]; scanf("%s%s",ch1,ch2); if(mp[ch1]==0) mp[ch1]=k++; if(mp[ch2]==0) mp[ch2]=k++; int x=mp[ch1]; int y=mp[ch2]; add(x,y); add(y,x); strcpy(mp1[x],ch1); strcpy(mp1[y],ch2); } solve(); if(flag>1) { printf("0 "); continue; } qsort(bridge,num,sizeof(bridge[0]),cmp); printf("%d ",num); for(i=0;i<num;i++) { int j=bridge[i]; j=j/2*2; int u=edge[j].u; int v=edge[j].v; printf("%s %s ",mp1[u],mp1[v]); } } }