首页 > 代码库 > 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],边<u,v>(我们假设dis[u]<=dis[v])如果满足dis[u]+1=dis[v],那么就将这条边加入第dis[v]个集合中去,其他不满足的边就随便放就好了。
具体算法的正确性就不给予证明了。
AC代码:
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <iostream> #include <vector> #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<dis[bian[p].num] && hash[bian[p].num]==0) { hash[bian[p].num]=1; dui[++duip]=bian[p].num; dis[bian[p].num]=dis[dui[i]]+1; } } hash[dui[i]]=0; } return; } int main() { scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=m;i++) { int p,q; scanf("%d%d",&p,&q); Add(p,q,i*2-1); Add(q,p,i*2); g[i][0]=p; g[i][1]=q; } SPFA(); vector <int> 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; }
sgu213-Strong Defence
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。