P1656 炸铁路

逃离我推掉我的手 2021-12-03 17:57 242阅读 0赞

我。。我。。我。。

我到底该说是良心贾还是黑心贾呢。。。

你说一道题，在洛谷（[洛谷题面][Link 1]）交一遍，UOJ（[UOJ题面][UOJ]）交一遍，这边过那边就不过，那边过这边就不过。。要死。。

好的从难度上来说呢还是很简单的（想不到一个月前黄题对我来说还是难题。。想都不敢想的那种。。），直接是tarjan板子+割桥结束

1 #include<cstdio>
     2 #include<cstdlib>
     3 #include<cstring>
     4 #include<iostream>
     5 #include<algorithm>
     6 
     7 #define  N 500005
     8 
     9 using namespace std;
    10 
    11 bool c[N];
    12 
    13 int n,m,x,y,s,tot,tim;
    14 
    15 int dfn[N],low[N],head[N];
    16 
    17 int read(){
    18     int x=0,f=1; char ch=getchar();
    19     while(ch<'0'||ch>'9'){
        if(ch=='-')f=-1; ch=getchar();}
    20     while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    21     return x*f;
    22 }
    23 
    24 struct edge{
    25     int from,to,next;
    26 }edge[N];
    27 
    28 void add(int x,int y){
    29     tot++;
    30     edge[tot].to=y;
    31     edge[tot].from=x;
    32     edge[tot].next=head[x];
    33     head[x]=tot;
    34 }
    35 
    36 struct nn{
    37     int x,y;
    38 }q[N];
    39 
    40 int cmp(nn a,nn b){
    41     if(a.x!=b.x){
    42         return a.x<b.x;
    43     }
    44     return a.y<b.y;
    45 }
    46 
    47 void tarjan(int now,int pre){
    48     dfn[now]=low[now]=++tim;
    49     for(int i=head[now];i;i=edge[i].next){
    50         int t=edge[i].to;
    51         if((1^i)==pre){
    52             continue;
    53         }
    54         if(!dfn[t]){
    55             tarjan(t,i);
    56             low[now]=min(low[now],low[t]);
    57             if(dfn[now]<low[t]){
    58                 c[i>>1]=true;
    59             }
    60         }
    61         else{
    62             low[now]=min(low[now],dfn[t]);
    63         }
    64     }
    65 }
    66 
    67 int main(){
    68     n=read();
    69     m=read();
    70     tot=1;
    71     for(int i=1;i<=m;i++){
    72         x=read();
    73         y=read();
    74         add(x,y);
    75         add(y,x);
    76     }
    77     for(int i=1;i<=n;i++){
    78         if(!dfn[i]) tarjan(i,-1);
    79     }
    80     for(int i=1;i<=m;i++){
    81         if(c[i]) {
    82             ++s;
    83             q[s].x=edge[i<<1].from;
    84             q[s].y=edge[i<<1].to;
    85             if(q[s].x>q[s].y){
    86                 swap(q[s].x,q[s].y);
    87             }
    88         }
    89     }
    90     sort(q+1,q+1+s,cmp);
    91     for(int i=1;i<=s;i++){
    92         printf("%d %d\n",q[i].x,q[i].y);
    93     }
    94     return 0;
    95 }

我的代码。。就是chaode，反正没人看得见嘤嘤嘤~~~

转载于:https://www.cnblogs.com/hahaha2124652975/p/11156566.html

[Link 1]: https://www.luogu.org/problemnew/show/P1656
[UOJ]: http://220.180.209.150:38888/problem/271