POJ 3164 Command Network

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<vector>
  6 #include<stack>
  7 #include<queue>
  8 #include<map>
  9 #include<cstdlib>
 10 #include<cmath>
 11 using namespace std;
 12 #define ll long long
 13 #define pb push_back
 14 //const double eps = 1e-8;
 15 const int maxn = 205;
 16 const int maxm = 10005;
 17 int g[maxn],pre[maxn],s[maxn];
 18 double x[maxn],y[maxn];
 19 double mc[maxn];
 20 bool vis[maxn];
 21 int nume,m,n,cnt,root;
 22 struct edge
 23 {
 24     int v,u,nxt;
 25     double c;
 26 } e[maxm * 2];
 27 void init()
 28 {
 29      memset(g,0,sizeof(g));
 30      nume = 1;
 31 }
 32 double dist(double x1,double y1,double x2,double y2)
 33 {
 34     return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
 35 }
 36 void addedge(int u,int v,double c)
 37 {
 38     if (u == v) return;
 39     ++nume;
 40     e[nume].u = u;
 41     e[nume].v = v;
 42     e[nume].c = c;
 43     e[nume].nxt = g[u];
 44     g[u] = nume;
 45 }
 46 void find_mincost()
 47 {
 48     memset(pre,0,sizeof(pre));
 49     for (int i = 1; i <= n; i++) mc[i] = 1000000000;
 50     for (int i = 1; i <= nume; i++)
 51         if (e[i].v != e[i].u)
 52     {
 53         if (mc[e[i].v] > e[i].c && e[i].v != root)
 54         {
 55             mc[e[i].v] = e[i].c;
 56             pre[e[i].v] = e[i].u;
 57         }
 58     }
 59 }
 60 bool dfs(int x,int y)
 61 {
 62     int z = pre[x];
 63     if (z == 0) return 0;
 64     if (s[z] == 0)
 65     {
 66         s[z] = cnt;
 67         if (!dfs(z,y)) s[z] = 0;
 68         else return 1;
 69     }
 70     else return z == y;
 71     return 0;
 72 }
 73 void flood(int x)
 74 {
 75     for (int i = g[x]; i; i = e[i].nxt)
 76         if (!s[e[i].v])
 77     {
 78         s[e[i].v] = 1;
 79         flood(e[i].v);
 80     }
 81 }
 82 bool check()
 83 {
 84     memset(s,0,sizeof(s));
 85     s[1] = 1;
 86     flood(1);
 87     for (int i = 1; i <= n; i++)
 88         if (!s[i]) return 0;
 89     return 1;
 90 }
 91 int main()
 92 {
 93     while (scanf("%d%d",&n,&m) != EOF)
 94     {
 95         for (int i = 1; i <= n; i++) scanf("%lf%lf",&x[i],&y[i]);
 96         init();
 97         int a,b;
 98         for (int i = 1; i <= m; i++)
 99         {
100             scanf("%d%d",&a,&b);
101             addedge(a,b,dist(x[a],y[a],x[b],y[b]));
102         }
103         if (!check())
104         {
105             puts("poor snoopy");
106             continue;
107         }
108        root = 1; cnt = n;
109        double ans = 0;
110        while (1)
111        {
112            find_mincost();
113            //for (int i = 1; i <= n; i++) cout<<i<<" "<<mc[i]<<" "<<pre[i]<<endl;
114            for (int i = 1; i <= n; i++)
115             if (i != root) ans += mc[i];
116            memset(s,0,sizeof(s));
117            cnt = 0;
118            int cir = 0;
119            for (int i = 1; i <= n; i++)
120               if (!s[i])
121               {
122                   cnt++;
123                   s[i] = cnt;
124                   if (dfs(i,i))
125                   {
126                       cir++;
127                   }
128               }
129             //cout<<root<<" "<<cnt<<" "<<cir<<endl;
130             //cout<<m<<endl;
131             if (cir == 0) break;
132             for (int i = 1; i <= nume; i++)
133             {
134                 int x = e[i].u,y = e[i].v;
135                 e[i].u = s[x]; e[i].v = s[y];
136                 if ((e[i].u != e[i].v))
137                 {
138                    //cout<<1<<endl;
139                     e[i].c -= mc[y];
140                 }
141             }
142             //for (int i = 1; i <= m; i++) cout<<e[i].u<<" "<<e[i].v<<" "<<e[i].c<<endl;
143         n = cnt;
144         root = s[root];
145        }
146        printf("%.2f\n",ans);
147     }
148     return 0;
149 }