POJ 3164 Command Network

看题秒打完结果T飞查错30分钟发现自己把i打成1了TAT 于是兴冲冲再交机房里只能听见我撕心裂肺的笑“哈哈哈哈哈哈哈终于从TLE变成WA了“ (MDZZ然后呢然后一个半小时过去了我查错到要吐了发现自己一个地方把db定义成int了哈哈哈哈哈哈哈哈哈哈哈哈哈一个晚上啊啊啊!一道裸题啊!!!!!!!!!我要去看眼科不要拦我!!!!!!!!
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<string>
 7 #include<cmath>
 8 #define inf 2000000000 
 9 #define db double
10 #define maxn 50000
11 using namespace std;
12 int n,m,mm,cnt;
13 struct hh{
14     db x,y;
15 }a[maxn];
16 struct hhh{
17     int u,v;
18     db z;
19 }b[maxn];
20 int pre[maxn],vis[maxn],id[maxn];
21 db in[maxn];
22 db zl(int p,int root){
23     db sum=0;
24     while (1){
25         for (int i=1;i<=p;++i) in[i]=inf;
26         memset(pre,-1,sizeof(pre));
27         for (int i=1;i<=m;++i){
28             int u=b[i].u,v=b[i].v;
29             db z=b[i].z;//就是这里啊啊啊啊啊我一开始还强行把每条边*1000才过的样例!
30             if (z<in[v]&&u!=v){
31                 in[v]=z;
32                 pre[v]=u;
33             }
34         }
35         for (int i=1;i<=p;++i){
36             if (i==root) continue;
37             if (in[i]==inf) return -1;
38         }
39         in[root]=0,cnt=0;
40         memset(vis,-1,sizeof(vis));
41         memset(id,-1,sizeof(id));
42         for (int i=1;i<=p;++i){
43             sum+=in[i];
44             int j=i;
45             while (j!=root&&vis[j]!=i&&id[j]==-1) vis[j]=i,j=pre[j];
46             if (j!=root&&id[j]==-1){
47                 ++cnt;
48                 for (int q=pre[j];q!=j;q=pre[q]) id[q]=cnt;
49                 id[j]=cnt;
50             }
51         }
52         if (cnt==0) break;
53         for (int i=1;i<=p;++i) if (id[i]==-1) id[i]=++cnt;
54         for (int i=1;i<=m;++i){
55             int u=b[i].u,v=b[i].v;
56             b[i].u=id[u];
57             b[i].v=id[v];
58             if (b[i].u!=b[i].v) b[i].z-=in[v];
59         }
60         root=id[root];
61         p=cnt;
62     }
63     return sum;
64 }
65 int main(){
66     freopen ("5.in","r",stdin);
67     freopen ("5.out","w",stdout);
68     while (scanf ("%d%d",&n,&m)!=EOF){
69         memset(b,0,sizeof(b));
70         memset(a,0,sizeof(a));
71         for (int i=1;i<=n;++i) scanf("%lf%lf",&a[i].x,&a[i].y);
72         for (int i=1;i<=m;++i){
73             int x,y;
74             scanf ("%d%d",&x,&y);
75             db o=sqrt((a[x].x-a[y].x)*(a[x].x-a[y].x)+(a[x].y-a[y].y)*(a[x].y-a[y].y));
76             b[i].u=x;b[i].v=y;b[i].z=o;
77         }
78         db ans=zl(n,1);
79         if (ans==-1) printf("poor snoopyn");
80         else printf("%.2fn",ans);
81     }
82     return 0;
83   }
今天 我学会了很多比如优雅地摔键盘 以及优雅地扇自己(微笑

相关内容推荐