[SPOJ962]Intergalactic Map 拆点+最大流
Jedi knights, Qui-Gon Jinn and his young apprentice Obi-Wan Kenobi, are entrusted by Queen Padmé Amidala to save Naboofrom an invasion by the Trade Federation. They must leave Naboo immediately and go to Tatooine to pick up the proof of the Federation’s evil design. They then must proceed on to the Republic’s capital planet Coruscant to produce it in front of the Republic’s Senate. To help them in this endeavor, the queen’s captain provides them with an intergalactic map. This map shows connections between planets not yet blockaded by the Trade Federation. Any pair of planets has at most one connection between them, and all the connections are two-way. To avoid detection by enemy spies, the knights must embark on this adventure without visiting any planet more than once. Can you help them by determining if such a path exists?
Note - In the attached map, the desired path is shown in bold.
Input Description
The first line of the input is a positive integer t ≤ 20, which is the number of test cases. The descriptions of the test cases follow one after the other. The first line of each test case is a pair of positive integers n, m (separated by a single space). 2 ≤ n ≤ 30011 is the number of planets and m ≤ 50011 is the number of connections between planets. The planets are indexed with integers from 1 to n. The indices of Naboo, Tatooine and Coruscant are 1, 2, 3 respectively. The next m lines contain two integers each, giving pairs of planets that have a connection between them.
Output Description
The output should contain t lines. The ith line corresponds to the ith test case. The output for each test case should be YES if the required path exists and NO otherwise.
Example
Input
2
3 3
1 2
2 3
1 3
3 1
1 3
Output
YES
NO
题目大意:
求是否存在1->2再从2->3的不重复路径
题解:
先拆点 保证每个点只经过一次 (i,i+n,1)。
然后 (s,2+n,2) (1,T,1)(3,T,1)最后看最大流是否等于2即可
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
const int N=,M=,INF=;
int gi(){
int str=;char ch=getchar();
while(ch>'' || ch<'')ch=getchar();
while(ch>='' && ch<='')str=str*+ch-'',ch=getchar();
return str;
}
int n,m,num=,head[N],s=,T;
struct Lin{
int next,to,dis;
}a[M*];
void init(int x,int y,int z){
a[++num].next=head[x];
a[num].to=y;
a[num].dis=z;
head[x]=num;
a[++num].next=head[y];
a[num].to=x;
a[num].dis=;
head[y]=num;
}
int q[N*],dep[N];
bool bfs()
{
memset(dep,,sizeof(dep));
q[]=s;dep[s]=;int t=,sum=,x,u;
while(t!=sum)
{
x=q[++t];
for(int i=head[x];i;i=a[i].next){
u=a[i].to;
if(dep[u]||a[i].dis<=)continue;
dep[u]=dep[x]+;q[++sum]=u;
}
}
return dep[T];
}
int dfs(int x,int flow)
{
if(x==T || !flow)return flow;
int u,tmp,sum=;
for(int i=head[x];i;i=a[i].next){
u=a[i].to;
if(dep[u]!=dep[x]+ || a[i].dis<=)continue;
tmp=dfs(u,min(flow,a[i].dis));
a[i].dis-=tmp;a[i^].dis+=tmp;
sum+=tmp;flow-=tmp;
if(!flow)break;
}
return sum;
}
int maxflow(){
int tmp,tot=;
while(bfs()){
tmp=dfs(s,INF);
while(tmp)tot+=tmp,tmp=dfs(s,INF);
}
return tot;
}
void work()
{
int x,y;
n=gi();m=gi();T=(n<<)+;
for(int i=;i<=n;i++)init(i,i+n,);
for(int i=;i<=m;i++){
x=gi();y=gi();
if(x>n || x< || y>n || y<)continue;
init(x+n,y,);init(y+n,x,);
}
init(s,+n,);init(,T,);init(,T,);
int tp=maxflow();
if(tp==)printf("YES\n");
else printf("NO\n");
}
void Clear(){
num=;
memset(head,,sizeof(head));
}
int main()
{
int TT=gi();
while(TT--){
work();
Clear();
}
return ;
}
最新文章
- SQL--子查询
- C# 谈Dictionary<;TKey,TValue>;,SortedDictionary<;TKey,TValue>;排序
- Protobuf一键生成代码bat文件
- Codeforces Round #282 (Div. 1) A. Treasure 水题
- paip.QQ音乐导出歌单总结
- poj 3487 稳定婚姻
- Java—异常处理总结
- iOS 自定义各类bar的属性
- 基于NIOS-II的示波器:PART3 初步功能实现
- Java课程设计——学生基本信息管理
- Apache POI - Java Excel APIs
- 770. Basic Calculator IV
- linux下安装mysql简单步骤
- SQL 事务 begin tran、commit tran、rollback tran 的用法
- (待解决,效率低下)47. Permutations II C++回溯法
- Ext JS isField为空或不是对象问题的解决
- org.apache.ibatis.binding.BindingException: Invalid bound statement (not found): 问题解决方法
- web项目中的执行流程参数传递详解
- Oracle PLSQL Demo - 12.定义包体[Define PACKAGE BODY]
- 前端异步文件上传组件 Uploader