首页 > 代码库 > HDU 3715 Go Deeper
HDU 3715 Go Deeper
Go Deeper
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2198 Accepted Submission(s): 722
Problem Description
Here is a procedure‘s pseudocode:
go(int dep, int n, int m)
begin
output the value of dep.
if dep < m and x[a[dep]] + x[b[dep]] != c[dep] then go(dep + 1, n, m)
end
In this code n is an integer. a, b, c and x are 4 arrays of integers. The index of array always starts from 0. Array a and b consist of non-negative integers smaller than n. Array x consists of only 0 and 1. Array c consists of only 0, 1 and 2. The lengths of array a, b and c are m while the length of array x is n. Given the elements of array a, b, and c, when we call the procedure go(0, n, m) what is the maximal possible value the procedure may output?
go(int dep, int n, int m)
begin
output the value of dep.
if dep < m and x[a[dep]] + x[b[dep]] != c[dep] then go(dep + 1, n, m)
end
In this code n is an integer. a, b, c and x are 4 arrays of integers. The index of array always starts from 0. Array a and b consist of non-negative integers smaller than n. Array x consists of only 0 and 1. Array c consists of only 0, 1 and 2. The lengths of array a, b and c are m while the length of array x is n. Given the elements of array a, b, and c, when we call the procedure go(0, n, m) what is the maximal possible value the procedure may output?
Input
There are multiple test cases. The first line of input is an integer T (0 < T ≤ 100), indicating the number of test cases. Then T test cases follow. Each case starts with a line of 2 integers n and m (0 < n ≤ 200, 0 < m ≤ 10000). Then m lines of 3 integers follow. The i-th(1 ≤ i ≤ m) line of them are ai-1 ,bi-1 and ci-1 (0 ≤ ai-1, bi-1 < n, 0 ≤ ci-1 ≤ 2).
Output
For each test case, output the result in a single line.
Sample Input
3
2 1
0 1 0
2 1
0 0 0
2 2
0 1 0
1 1 2
Sample Output
112
Author
CAO, Peng
Source
2010 Asia Chengdu Regional Contest
题目的意思是求出符合条件的能去到的最大深度 。
然后 x 只有 0 , 1 两种 。
明显就是一个 two - sat .
然后二分一个深度 , 重新构图 , 看下所有限制能否都符合 。
卡了一下二分 。 。
构图我是反向的 , 即 u - v 表示这两个条件不能共存
#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <map>using namespace std;typedef long long LL;const int N = 20010;const int M = 800010;int eh[N] , et[M], nxt[M] , tot ;bool mark[N] ;int n , s , a[N] , b[N] ,c[N];int st[N] , top ;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++;}void init(){ memset (mark , false , sizeof mark ); tot = 0 ; memset ( eh , -1 , sizeof eh );}// ----------------bool dfs( int u ){ if( mark[u] ) return true ; if( mark[u^1] ) return false ; mark[u] = true; st[top++] = u ; for( int i = eh[u] ; ~i ; i = nxt[i] ){ int v = et[i] ; if( !dfs( v^1 ) ) return false; } return true ;}bool solve( int m ){ init(); for( int i = 0 ; i < m ; ++i ){ if( c[i] == 0 ){ addedge( 2*a[i] , 2*b[i] ); } else if( c[i] == 1 ){ addedge( (2*a[i])^1 , 2*b[i] ); addedge( (2*b[i])^1 , 2*a[i] ); } else { addedge( (2*a[i])^1 , (2*b[i])^1 ); } } for( int i = 0 ; i < 2 * n ; i+=2 ){ if( !mark[i] && !mark[i+1] ){ top = 0 ; if( !dfs(i) ){ while( top > 0 ) mark[ st[--top] ] = false ; if( !dfs(i+1) ) return false ; } } } return true;}void run(){ int m ; scanf("%d%d",&n,&m); for( int i = 0 ; i < m ;++i ) scanf("%d%d%d",&a[i],&b[i],&c[i]); int ans = 1 , l = 1 ,r = m ; while( l <= r ){ int mid = ( l + r ) / 2;// cout << mid <<‘ ‘<<endl ; if( solve(mid) ) l = mid + 1 , ans = mid ; else r = mid - 1; } printf("%d\n",ans);}int main(){ #ifdef LOCAL freopen("in","r",stdin); #endif int _ ; scanf("%d",&_); while( _ -- )run(); return 0;}
HDU 3715 Go Deeper
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。