bzoj 1093: [ZJOI2007]最大半连通子图-白红宇

bzoj 1093: [ZJOI2007]最大半连通子图

阅读量：5295 次

发布时间：2019-06-14

本文共 925 字，大约阅读时间需要 3 分钟。

2016-06-21

读一下题目，发现环内肯定在一个半联通子图内，于是先tarjan缩点，然后就是找这个图的最长链及数目。拓扑一下即可。

注意注意此题一定要将边进行判重。

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
            8 #define ll long long 9 #define M 2000009 10 using namespace std; 11 ll read() 12 { 13 char ch=getchar(); 14 ll x=0,f=1; 15 for(;ch<'0'||ch>'9';ch=getchar()) 16 if(ch=='-') 17 f=-1; 18 for(;ch>='0'&&ch<='9';ch=getchar()) 19 x=x*10+ch-'0'; 20 return x*f; 21 } 22 int du[M],dfn[M],low[M],K,n,m,tot,head[M],next[M],u[M],belong[M],cnt,T,q[M],sum,he[M]; 23 bool f[M]; 24 int ss; 25 struct data 26 { 27 int d,s; 28 }a[M],qq[M]; 29 bool cmp(data a1,data a2) 30 { 31 if(a1.s==a2.s) 32 return a1.d
            
             mx)127 {128 mx=a[i].d;129 mxx=a[i].s;130 }131 }132 printf("%d\n%d",mx,mxx);133 return 0;134 }