首页 > 代码库 > [zjoi2004]嗅探器
[zjoi2004]嗅探器
某军搞信息对抗实战演习.红军成功地侵入了蓝军的内部网络.
蓝军共有两个信息中心.红军计划在某台中间服务器上安装一个嗅探器,从而能够侦听到两个信息中心互相交换的所有信息.但是蓝军的网络相当的庞大,数据包从一个信息中心传到另一个信息中心可以不止有一条通路.现在需要你尽快地解决这个问题.应该把嗅探器安装在哪个中间服务器上才能保证所有的数据包都能被捕获?
题解:tarjan的简单应用;
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<ctime> #include<cmath> #include<set> #include<map> #include<queue> #include<algorithm> #include<iomanip> using namespace std; #define FILE "dealing" #define up(i,j,n) for(int i=(j);i<=(n);i++) #define pii pair<int,int> #define LL int #define mem(f,g) memset(f,g,sizeof(f)) namespace IO{ char buf[1<<15],*fs,*ft; int gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?-1:*fs++;} int read(){ int ch=gc(),f=0,x=0; while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=1;ch=gc();} while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+ch-‘0‘;ch=gc();} return f?-x:x; } int readint(){ int ch=getchar(),f=0,x=0; while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=(x<<1)+(x<<3)+ch-‘0‘;ch=getchar();} return f?-x:x; } }using namespace IO; const int maxn=101000,inf=100000000; int n,m; int s,t,x,y; struct node{ int y,next; }e[maxn<<1]; int len=0,linkk[maxn]; void insert(int x,int y){e[++len].y=y;e[len].next=linkk[x];linkk[x]=len;} int pre[maxn],low[maxn],fa[maxn],dfs_clock=0; int ans=inf; void updata(int x){if(x!=s&&x!=t)if(ans>x)ans=x;} int tarjan(int x){ int flag=0,h; if(x==t)flag=1; low[x]=pre[x]=++dfs_clock; for(int i=linkk[x];i;i=e[i].next){ if(e[i].y==fa[x])continue; fa[e[i].y]=x; if(!pre[e[i].y]){ if(h=tarjan(e[i].y))flag=1; if(h&&low[e[i].y]>=pre[x])updata(x); if(low[e[i].y]<low[x])low[x]=low[e[i].y]; } else if(pre[e[i].y]<low[x])low[x]=pre[e[i].y]; } return flag; } int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); n=read(); while(true){ x=read(),y=read(); if(!x&&!y)break; insert(x,y);insert(y,x); } s=read(),t=read(); tarjan(s); if(ans!=inf)printf("%d\n",ans); else printf("No solution\n"); return 0; }
[zjoi2004]嗅探器
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。