网站安全和信息化建设,郑州平面设计公司,wordpress情侣博客,邢台网络运营中心题目链接 https://vjudge.net/problem/HihoCoder-1689有N个整数A1, A2, ... AN#xff0c;现在我们知道M条关于这N个整数的信息。每条信息是#xff1a;Ai Aj 或者 Ai Aj 小Hi希望你能从第一条信息开始依次逐条处理这些信息。一旦能推断出A1和AN的大小关系就立即停止。… 题目链接 https://vjudge.net/problem/HihoCoder-1689有N个整数A1, A2, ... AN现在我们知道M条关于这N个整数的信息。每条信息是Ai Aj 或者 Ai Aj 小Hi希望你能从第一条信息开始依次逐条处理这些信息。一旦能推断出A1和AN的大小关系就立即停止。 输出在处理第几条时第一次推断出A1和AN的关系。如果处理完全部M条信息还是不知道A1和AN的大小关系输出-1。 保证M条信息是没有矛盾的。Input第一行包含两个整数N和M。 以下M行每行包含一条信息Ai Aj 或者 Ai Aj。 对于30%的数据1 ≤ N ≤ 1000, 1 ≤ M ≤ 10000 对于100%的数据1 ≤ N ≤ 100000, 1 ≤ N ≤ 1000000Output一个整数表示答案。Sample Input5 8
A1 A3
A3 A2
A3 A4
A5 A2
A1 A4
A1 A2
A5 A1
A5 A3Sample Output7【思路】 图论基础二分法 如果ab就加一条有向边a-b如果ab就加两条有向边a-b和b-a然后用一个变量index记录这条边是输入中从上往下数的第几条边,采用二分法判断前x条边内否判断出最终的大小关系在二分的时候要用两次dfs一次是看能否从起点走到终点另一次是从终点到起点只要有一次连通着就可以dfs搜索的时候所经过的边不能超过mid,最后就能出答案了。输入格式比较坑我也是看另一个人的题解才知道的。#includebits/stdc.h
using namespace std;const int maxn 1e5 50;
const int maxm 1e6 50;int n, m, from, to;
int le, ri, mid;
char op[2];struct node {int to, index;node(int t, int in) :to(t), index(in) {}
};bool used[maxn];
vectornode g[maxn];void init() {for (int i 0; i maxn; i) g[i].clear();
}bool dfs1(int u) {if (u 1) return 1;used[u] 1;for (int i 0; i g[u].size(); i) {node e g[u][i];if (e.index mid) continue;if (used[e.to]) continue;if (dfs1(e.to)) return 1;}return 0;
}bool dfs2(int u) {if (u n) return 1;used[u] 1;for (int i 0; i g[u].size(); i) {node e g[u][i];if (e.index mid) continue;if (used[e.to]) continue;if (dfs2(e.to)) return 1;}return 0;
}int main() {init();scanf(%d%d , n, m);for (int i 1; i m; i) {getchar();scanf(%d , from);scanf(%s , op);getchar();scanf(%d , to);if (from to) continue;if ( op[0]) {g[from].push_back(node(to, i));}else if ( op[0]) {g[from].push_back(node(to, i));g[to].push_back(node(from, i));}}if (n 1) {printf(0\n);return 0;} int ans -1;le 0, ri m;while (le 1 ri) {mid (le ri) 1;memset(used, 0, sizeof(used));bool ok dfs1(n);memset(used, 0, sizeof(used));if (ok || dfs2(1)) { ans mid; ri mid; }else { le mid; }}printf(%d\n, ans);return 0;
} 转载于:https://www.cnblogs.com/wafish/p/10465453.html
