sgu213-Strong Defence

题目大意：

给你一个无向图，然后一个s，t表示起点和终点，然后输入n，m，s，t，将m条无相边分成L个集合，使得任意一个集合的边被去掉后，都不能从t到达s（或者是s到达t，具体不记得了，但是差不多吧。。。。。），然后要你求出最大的L，然后输出每一个边集。

解题思路：

首先看到要使得不能到达，我想到了网络流，但是后来想想发现，其实很简单。

先以s为起点跑一遍最短路，然后会得到一个dis[t]表示s到t的最短距离，然后L=dis[t]

之后就是将边分组，对于i=1~dis[t]，边 （我们假设dis[u]<=dis[v]）如果满足dis[u]+1=dis[v]，那么就将这条边加入第dis[v]个集合中去，其他不满足的边就随便放就好了。

具体算法的正确性就不给予证明了。

AC代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #define MAX(a,b) ((a)>(b)?(a):(b)) #define MIN(a,b) ((a)>(b)?(b):(a)) using namespace std; int n,m,s,t; struct bian_ { int num; int next; }bian[160010]={{0,0}}; int g[160010][2]={{0}}; int First[410]={0}; int dis[410]={0}; int hash[410]={0}; int dui[1000010]={0}; inline void Add(int p,int q,int k) { bian[k].num=q; bian[k].next=First[p]; First[p]=k; return; } void SPFA() { int duip=1; memset(dis,0x3f3f3f3f,sizeof(dis)); dis[s]=0; dui[duip]=s; hash[s]=1; for(int i=1;i<=duip;i++) { for(int p=First[dui[i]];p!=0;p=bian[p].next) { if(dis[dui[i]]+1
         
           ans[410]; for(int i=1;i<=m;i++) { int p=dis[g[i][0]],q=dis[g[i][1]]; if(p>q) swap(p,q); if(q==p+1) { if(q>=dis[t]) ans[dis[t]].push_back(i); else ans[q].push_back(i); } else ans[dis[t]].push_back(i); } printf("%d\n",dis[t]); for(int i=1;i<=dis[t];i++) { printf("%d ",ans[i].size()); for(int j=ans[i].size()-1;j>=0;j--) printf("%d%c",ans[i][j],j==0?'\n':' '); } return 0; }