分而治之,各个击破是兵家常用的策略之一。在战争中,我们希望首先攻下敌方的部分城市,使其剩余的城市变成孤立无援,然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序,判断每个方案的可行性。
输入在第一行给出两个正整数 N 和 M(均不超过10 000),分别为敌方城市个数(于是默认城市从 1 到 N 编号)和连接两城市的通路条数。随后 M 行,每行给出一条通路所连接的两个城市的编号,其间以一个空格分隔。在城市信息之后给出参谋部的系列方案,即一个正整数 K (≤ 100)和随后的 K 行方案,每行按以下格式给出:
Np v[1] v[2] ... v[Np]其中 Np 是该方案中计划攻下的城市数量,后面的系列 v[i] 是计划攻下的城市编号。
对每一套方案,如果可行就输出YES,否则输出NO。
刚开始看到这道题,我的第一个思路就是查和断,最后找一下。但是是这样的
map<int,map<int,int> >AT这样似乎建立了一个模拟版的 二维数组,我现在要做的事情 首先是赋值 比如 1 2 之间有联系 就AT[1][2]=true;
就这样我们录入之后,如样例所示,是这样子的
都是 TRUE。然后我们看下面
第一个测试样例 返回 NO 为什么返回no呢?我们把这些数字在上图中,只要含有的区域划掉,看看
是不是没有划完??对!没有划完就是NO。我们看看第二个例子
我们划划看
划完了,所以是YES 大体思路就是这样,可是,硬伤就来了,假定有1W组数据的情况,我要做的是找,划,再遍历一次看看有没有没有划掉的。map只能find到 KEY值 VALUE的值无法直接去find ,所以动用循环一定会爆炸超时的。想了很多办法,比如三容器+find法都报了超时。难道这就无解了吗。我们看一下我超时的代码:
#include <bits/stdc++.h> using namespace std; vector<int>AS1; vector<int>AS2; vector<bool>AS3; int betafind(vector<int>ADT, vector<bool>AS3, int pd) { int cnt = 0; for (int i = 0; i < ADT.size(); i++) { for (vector<int>::iterator it = AS1.begin(); it = find(it, AS1.end(), ADT[i]), it != AS1.end(); it++) { if (AS3[it - AS1.begin()]) AS3[it - AS1.begin()] = false, cnt++; } for (vector<int>::iterator it = AS2.begin(); it = find(it, AS2.end(), ADT[i]), it != AS2.end(); it++) { if (AS3[it - AS2.begin()]) AS3[it - AS2.begin()] = false, cnt++; } } return pd == cnt ? 1 : 0; } void betasolve() { int lu, gx; cin >> lu >> gx; for (int i = 0; i < gx; i++) { int t, p; cin >> t >> p; AS1.push_back(t); AS2.push_back(p); AS3.push_back(true); } int ts; cin >> ts; for (int ii = ts; ii--;) { int c; cin >> c; vector<int>TST; for (int sn = c; sn--;) { int gg; cin >> gg; TST.push_back(gg); } if (betafind(TST, AS3, gx)) cout << "YES" << endl; else cout << "NO" << endl; } } int main() { betasolve(); return 0; }额,真的不是 cin>> 和 cout << 拖的时间。我自以为用 find会缩短一些时间,再通过指针计算出位置,再用 第三个bool的容器去修改会加快速度。不对!感觉容器的find超级的鸡肋。还不如你直接去for ,专门骗我这些小白去用这些东西。
果然,我自以为好的代码,报了两个超时,心情很坏.因此几天饭吃不好,觉睡不好。我甚至还有以下思路,但是还没有去实现:
(一下每一点都代表个独立的思路,不是 过程)
1.用生成树来找,先把关系通过一定的条件连接然后把要删除的节点的值设置为-1,然后从头到尾遍历,去访问各个节点,然后每访问一个节点之前都去检查当前节点是不是-1,是的话就把计数器给我加一下,最后来几个判断。
2.把要删除的节点从原来的关系之中更改为-1,然后,把它们连接起来,只要每一个节点均指向-1那个节点,那么说明节点断开,最后再来一个判断。
3.使用一个布尔类型的标记数组存下我待删除的 节点位置所在的区域BOOL值为 false ,然后把点一一给我代入,来一个判断,如果 vis[原数据1]==true&&vis[原数据2]==true 那么就证明没有断,否则就是断了 因为关系里 不会有 这样的数据 1 2 又来个 2 1 感觉这样也没什么卵用。
然后想了一下,然后,在群里问了,她说遍历一遍就行了,让我有了对第三种方法起了好感。好 第三种 就这样完成了,我最后还在考虑能不能用 map<bool>去替换那个该死的 1W的数组,想想 算了 ,毕竟 memset摆在那里呢!你能对map用memset吗?这简直就是瞎扯。
好 看下代码,比较简单,修正了部分地方,使得代码AC了 【真的好那么,学长竟然说那么肉麻的话给某位女生。算了,毕竟我是不想结婚的人,单身很好,可以提升生活水平,伤心的时候世界把我忘了反而会让别人开心呢!】
#include <bits/stdc++.h> using namespace std; bool text[10000+2]; int tx, px; void solve() { pair<int, int>P[10000 + 2]; scanf("%d%d",&tx,&px); for (int i = 0; i<px;i++) { int x, y; scanf("%d%d", &x, &y); P[i] = { x,y }; } int tcx; scanf("%d",&tcx); for (int i = tcx; i--;) { int apx; scanf("%d", &apx); memset(text, 1, sizeof(text)); for (int j = apx; j--;) { int xc; scanf("%d",&xc); text[xc] = 0; } bool tecc; for (int n = 0; n < px; n++) { if (text[P[n].first] && text[P[n].second]) tecc = false, n = px; else tecc = true; } if (tecc) printf("YES\n"); else printf("NO\n"); } } int main() { solve(); // system("pause"); return 0; }