HDU 1816 Get Luffy Out *
Get Luffy Out *
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 570 Accepted Submission(s): 225
Behind the large door, there is a nesting prison, which consists of M floors. Each floor except the deepest one has a door leading to the next floor, and there are two locks in each of these doors. Ratish can pass through a door if he opens either of the two locks in it. There are 2N different types of locks in all. The same type of locks may appear in different doors, and a door may have two locks of the same type. There is only one key that can unlock one type of lock, so there are 2N keys for all the 2N types of locks. These 2N keys were made N pairs,one key may be appear in some pairs, and once one key in a pair is used, the other key will disappear and never show up again.
Later, Ratish found N pairs of keys under the rock and a piece of paper recording exactly what kinds of locks are in the M doors. But Ratish doesn't know which floor Luffy is held, so he has to open as many doors as possible. Can you help him to choose N keys to open the maximum number of doors?
0 3
1 2
4 5
0 1
0 2
4 1
4 2
3 5
2 2
0 0
题目有更改!
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <map>
#include <cmath>
#include <vector>
using namespace std;
const int N = (<<); int n , m , st[N<<] ,top;
int eh[N] , et[N*N] , nxt[N*N] , tot ;
bool mark[N<<]; struct node
{
int x , y ;
} key[N<<] , door[N<<]; void init()
{
tot = ;
memset( eh , - , sizeof eh );
memset( mark ,false , sizeof mark );
} void addedge( int u , int v )
{
et[tot] = v , nxt[tot] = eh[u] , eh[u] = tot++ ;
et[tot] = u , nxt[tot] = eh[v] , eh[v] = tot++ ;
} bool dfs( int u )
{
if( mark[u] ) return true;
if( mark[u^] ) return false ;
mark[u] = true ;
st[top++] = u ;
for( int i = eh[u] ; ~i ; i = nxt[i] ){
int v = et[i];
if( !dfs(v^) ) return false;
}
return true;
} bool solve()
{
for( int i = ; i < * n ; i += ){
if( !mark[i] && !mark[i+] ){
top = ;
if( !dfs(i) ){
while( top > ) mark[ st[--top] ] = false ;
if( !dfs(i+) ) return false;
}
}
}
return true;
} bool test( int dep )
{
init();
for( int i = ; i < n ; ++i ){
addedge( *key[i].x , *key[i].y );
}
for( int i = ; i < dep ; ++i ){
addedge(*door[i].x^,*door[i].y^);
}
return solve();
} void run()
{
int x , y ;
// cout << N <<endl;
for( int i = ; i < n ; ++i ){
scanf("%d%d",&key[i].x,&key[i].y);
} for( int i = ; i < m ; ++i ){
scanf("%d%d",&door[i].x,&door[i].y);
} int l = , r = m , ans = ;
while( l <= r )
{
int mid = ( l+r )>>;
if( test(mid) ) ans = mid , l = mid + ;
else r = mid - ;
}
printf("%d\n",ans);
} int main()
{
#ifdef LOCAL
freopen("in.txt","r",stdin);
#endif // LOCAL
while( scanf("%d%d",&n,&m) ){
if( !n && !m ) break;
run();
}
}
最新文章
- java的栈图形演示
- Node.js用ES6原生Promise对异步函数进行封装
- Java多线程开发系列之番外篇:事件派发线程---EventDispatchThread
- 用jQuery编的一个分页小代码
- UVa 11300 Spreading the Wealth(有钱同使)
- 微信域名weixin.com天价成交!是腾讯吗?
- webstorm &; phpstorm破解
- webpack echarts配置实例
- [Angular Tutorial]PhoneCat Tutorial App
- Spark机器学习之协同过滤算法
- 如何用jQuery实现div随鼠标移动而移动(详解)?----2017-05-12
- Numpy入门 - 行列式转置
- Linux服务器配置(一)
- 蓝桥每周一题之1. 3n+1 问题
- Maven遇到github引用的项目有bug怎么办?
- 算法提高 11-1实现strcmp函数
- MyEclipse如何清除废弃的工作空间
- 类的调用1(被调用的MyFirstJava)
- 局域网内远程连接OPC配置方法详解
- BBS--后台管理页面,编辑文章,xss攻击