Go Deeper HDU - 3715(2 - sat 水题 妈的 智障)

Go Deeper

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 3435    Accepted Submission(s): 1125

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?

 
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
1
1
2
 
Author
CAO, Peng
 
Source
 
Recommend
zhouzeyong
 
 
 
解析:
  一定要明确 是哪两个点
  然后建图一定要明确怎么建
  二分定要写对
 
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <cctype>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rep(i, a, n) for(int i=a; i<n; i++)
#define lap(i, a, n) for(int i=n; i>=a; i--)
#define lep(i, a, n) for(int i=n; i>a; i--)
#define rd(a) scanf("%d", &a)
#define rlld(a) scanf("%lld", &a)
#define rc(a) scanf("%c", &a)
#define rs(a) scanf("%s", a)
#define pd(a) printf("%d\n", a);
#define plld(a) printf("%lld\n", a);
#define pc(a) printf("%c\n", a);
#define ps(a) printf("%s\n", a);
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = 1e5 + , INF = 0x7fffffff, LL_INF = 0x7fffffffffffffff;
int n, m;
int a[maxn], b[maxn], c[maxn];
vector<int> G[maxn];
int sccno[maxn], low[maxn], vis[maxn], scc_clock, scc_cnt;
stack<int> S;
void init()
{
for(int i = ; i < maxn; i++) G[i].clear();
mem(sccno, );
mem(low, );
mem(vis, );
scc_clock = scc_cnt = ;
} void dfs(int u)
{
low[u] = vis[u] = ++scc_clock;
S.push(u);
for(int i = ; i < G[u].size(); i++)
{
int v = G[u][i];
if(!vis[v])
{
dfs(v);
low[u] = min(low[u], low[v]);
}
else if(!sccno[v])
low[u] = min(low[u], vis[v]);
}
if(vis[u] == low[u])
{
scc_cnt++;
for(;;)
{
int x = S.top(); S.pop();
sccno[x] = scc_cnt;
if(x == u) break;
}
}
} void build(int mid)
{
for(int i = ; i <= mid; i++)
{
if(c[i] == )
{
G[a[i] << | ].push_back(b[i] << );
G[b[i] << | ].push_back(a[i] << );
}
else if(c[i] == )
{
G[a[i] << | ].push_back(b[i] << | );
G[b[i] << | ].push_back(a[i] << | );
G[a[i] << ].push_back(b[i] << );
G[b[i] << ].push_back(a[i] << );
}
else if(c[i] == )
{
G[a[i] << ].push_back(b[i] << | );
G[b[i] << ].push_back(a[i] << | );
}
}
} bool check()
{
for(int i = ; i < n * ; i += )
if(sccno[i] == sccno[i + ])
return false;
return true;
} int main()
{
int T;
rd(T);
while(T--)
{
init();
rd(n), rd(m);
for(int i = ; i < m; i++)
{
rd(a[i]), rd(b[i]), rd(c[i]);
}
int l = , r = m;
while(l + < r)
{
init();
int mid = (l + r) / ;
build(mid);
for(int i = ; i < n * ; i++)
if(!vis[i]) dfs(i);
if(check()) l = mid;
else r = mid;
}
pd(l + ); } return ;
}
 
 
 

Go Deeper

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 3435    Accepted Submission(s): 1125

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?

 
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
1
1
2
 
Author
CAO, Peng
 
Source
 
Recommend
zhouzeyong
 
上一篇:Golang map并发 读写锁


下一篇:第四次作业——关于石墨文档(Android)客户端的案例分析