hdu 4005 The war

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cstdlib>
  5 #include<cmath>
  6 #include<algorithm>
  7 #include<vector>
  8 #define inf 0x7fffffff
  9 using namespace std;
 10 const int maxn=10000+10;
 11 const int M = 2e5+100;
 12 int n,m;
 13 struct Edge
 14 {
 15     int u,v,cost;
 16     int next;
 17 }edge[M];
 18 int head[maxn],edgenum;
 19 void add(int u,int v,int cost)
 20 {
 21     Edge E={u,v,cost,head[u] };
 22     edge[edgenum]=E;
 23     head[u]=edgenum++;
 24 
 25     Edge E1={v,u,cost,head[v] };
 26     edge[edgenum]=E1;
 27     head[v]=edgenum++;
 28 }
 29 
 30 int pre[maxn],low[maxn],dfs_clock,bcc_cnt,index;
 31 int mark[maxn];
 32 vector< vector<Edge> > dfsmap;
 33 vector<int> vec;
 34 int color[maxn];
 35 int dfs(int u,int fa)
 36 {
 37     low[u]=pre[u]= ++dfs_clock;
 38     int flag=1;
 39     for (int i=head[u] ;i!=-1 ;i=edge[i].next)
 40     {
 41         int v=edge[i].v;
 42         if (v==fa && flag) {flag=0;continue; }
 43         if (!pre[v])
 44         {
 45             dfs(v,u);
 46             low[u]=min(low[u],low[v]);
 47         }
 48         else if (pre[v]<pre[u])
 49         low[u]=min(low[u],pre[v]);
 50     }
 51 }
 52 void tarjan(int u,int fa){
 53     vec.push_back(u);
 54     pre[u]=low[u]=index++;
 55     mark[u]=true;
 56     bool flag=true;
 57     for(int i=head[u] ;i!=-1 ;i=edge[i].next){
 58         int d=edge[i].v;
 59         if(d==fa && flag){flag=false;continue;}
 60         if(!pre[d]){
 61             tarjan(d,u);
 62             low[u]=min(low[u],low[d]);
 63         }else {
 64             low[u]=min(low[u],pre[d]);
 65         }
 66     }
 67     if(low[u]==pre[u]){
 68         int d;
 69         bcc_cnt++;
 70         do{
 71             d=vec.back();
 72             vec.pop_back();
 73             color[d]=bcc_cnt;
 74             mark[d]=false;
 75         }while(d!=u);
 76     }
 77 }
 78 void find_bcc()
 79 {
 80     memset(pre,0,sizeof(pre));
 81     memset(low,0,sizeof(low));
 82     memset(mark,false,sizeof(mark));
 83     vec.clear();
 84     dfs_clock=bcc_cnt=0;
 85     index=1;
 86     for (int i=1 ;i<=n ;i++)
 87     if (!pre[i]) tarjan(i,-1);
 88 }
 89 int mindistance;
 90 pair<int,int> dfs2(int u,int fa)
 91 {
 92     int first=inf,second=inf;
 93     for (int i=0 ;i<dfsmap[u].size() ;i++)
 94     {
 95         int v=dfsmap[u][i].v;
 96         int w=dfsmap[u][i].cost;
 97         if (v==fa) continue;
 98         pair<int,int> tmp=dfs2(v,u);
 99         if (tmp.first>w) swap(tmp.first,w);
100         //if (second>w) second=w;
101         if (tmp.first<first)
102         {
103             second=min(tmp.second,first);
104             first=tmp.first;
105         }
106         else if (tmp.first<second) second=tmp.first;
107     }
108     return make_pair(first,second);
109 }
110 int main()
111 {
112     int a,b,c;
113     while (scanf("%d%d",&n,&m)!=EOF)
114     {
115         memset(head,-1,sizeof(head));
116         edgenum=0;
117         for (int i=0 ;i<m ;i++)
118         {
119             scanf("%d%d%d",&a,&b,&c);
120             add(a,b,c);
121         }
122         find_bcc();
123         cout<<endl<<bcc_cnt<<endl;
124         for (int i=1 ;i<=n ;i++)
125         cout<<i<<"  "<<low[i]<<"  "<<color[i]<<endl;
126         cout<<endl;
127         dfsmap.resize(n+10);
128         for (int i=1 ;i<n+10 ;i++) dfsmap[i].clear();
129         int mindist=inf,uu=0,vv=0;
130         for (int i=0 ;i<edgenum ;i++)
131         {
132             int u=edge[i].u;
133             int v=edge[i].v;
134             int w=edge[i].cost;
135             int u1=color[u] ,v1=color[v] ;
136             if (u1 != v1)
137             {
138                 Edge E={u1,v1,edge[i].cost };
139                 dfsmap[u1].push_back(E);
140                 if (edge[i].cost<mindist)
141                 {
142                     mindist=edge[i].cost;
143                     uu=u1 ;vv=v1 ;
144                 }
145             }
146         }
147 //        for (int i=1 ;i<=n ;i++)
148 //        {
149 //            int u=low[i];
150 //            for (int j=head[i] ;j!=-1 ;j=edge[j].next)
151 //            {
152 //                int v=low[edge[j].v ];
153 //                if (u!=v)
154 //                {
155 //                    Edge E={u,v,edge[j].cost };
156 //                    dfsmap[u].push_back(E);
157 //                    if (edge[j].cost<mindist)
158 //                    {
159 //                        mindist=edge[j].cost;
160 //                        uu=u ;vv=v ;
161 //                    }
162 //                }
163 //            }
164 //        }
165         mindistance=inf;
166         pair<int,int> p1=dfs2(uu,vv);
167         pair<int,int> p2=dfs2(vv,uu);
168         //pair<int,int> p1=dfs3(uu,vv);
169         //pair<int,int> p2=dfs3(vv,uu);
170         mindistance=min(mindistance,min(p1.second,p2.second));
171         printf("%d\n",mindistance==inf ? -1 : mindistance);
172     }
173     return 0;
174 }