sgu213-Strong Defence

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;
}