原题：Now or later 原题大意每架飞机有早晚起降两种方式，给定n架飞机两种方式的起落时间，为每架飞机安排起落时间（早或晚），使得所有飞机起降时间按照早到晚的顺序之间的间隔时间最小值尽量大。 算法分析最小时间尽量大应该采用二分的方法比较好，然后就变成了判别某个时间间隔m是不是符合要求的了。为没加飞机设立一个变量xi，0表示早，1表示晚，然后每架飞机i用两个点2i,2i+1表示，前者如果被标记表示早，后者被标记表示晚降。 然后对不同的飞机的起降时间中间隔小于m的i，j建立约束条件，例如：i架飞机早降间隔和j架飞机的早降时间间隔小于m，那么约束条件就可以在图中这样表示：建立两条边2i—>2j+1, 2j->2i+1，表示如果i早降则j必须晚降，j早降i必须晚降。 程序代码#include <bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define pb push_back using namespace std; typedef long long ll; const int maxn = 2 ...

原题：Proving Equivalences 原题大意给出N个命题，要求你证明这N个命题的等价性：比如有4个命题a,b,c,d，我们证明a<->b, b<->c,c<->d，每次证明都是双向的，因此一共用了6次推导如果换成证明a->b,b->c,c->d,d->a,每次证明都是单向的，而只需4次就可以证明所有命题的等价性现在给出M个命题证明，问还需要证明几个，才可以保证N个命题等价。 算法分析缩点后求DAG中入度为0和出度为0的联通块的较大值 程序代码#include <bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define pb push_back using namespace std; typedef long long ll; const int maxn = 2e4+5; vector<int> G[maxn]; int pre[maxn], lowlink[maxn], sccno[maxn], dfs_clock, sc ...

原题：Knights of the Round Table 原题大意有n个骑士经常举行圆桌会议，每次圆桌会议至少要有3个骑士参加(且每次参加的骑士数量是奇数个)，且所有互相憎恨的骑士不能坐在圆桌旁的相邻位置，问有多少个骑士不可能参加任何一个会议 算法分析以骑士为点建立无向图G。如果两个骑士可以相邻(即他们并不互相憎恨)，即可连一条边。则题目就转化为求不在任何一个简单奇圈上的结点个数首先，圈就是一个双连通的分量，所以第一件事就是将所有的双连通分量求出来，接着再判定这个双连通分量是不是奇圈奇圈的判定就是用二分图染色判定，如果某个圈能被二分图染色，那么这个圈必然不是奇圈，因为二分图染色，染色的点是成对的，所以点的数量是偶数的 程序代码#include <bits/stdc++.h> #define mem(a,b) memset(a,b,sizeof(a)) #define pb push_back using namespace std; const int maxn = 1e3+5; int color[maxn], odd[maxn]; int pre[maxn], is ...

原题：Road Construction 原题大意某个企业想把一个热带天堂岛变成旅游胜地，岛上有N个旅游景点，任意2个旅游景点之间有路径连通（注意不一定是直接连通）。而为了给游客提供更方便的服务，该企业要求道路部门在某些道路增加一些设施。道路部门每次只会选择一条道路施工，在该条道路施工完毕前，其他道路依然可以通行。然而有道路部门正在施工的道路，在施工完毕前是禁止游客通行的。这就导致了在施工期间游客可能无法到达一些景点。为了在施工期间所有旅游景点依然能够正常对游客开放，该企业决定搭建一些临时桥梁，使得不管道路部门选在哪条路进行施工，游客都能够到达所有旅游景点。给出当下允许通行的R条道路，问该企业至少再搭建几条临时桥梁，才能使得游客无视道路部门的存在到达所有旅游景点？ 算法分析 http://blog.csdn.net/lyy289065406/article/details/6762370 程序代码#include <iostream> #include <cstring> #include <vector> #include <algorit ...

原题：Network 原题大意求割顶的模板题。 程序代码#include <iostream> #include <cstdio> #include <vector> #include <sstream> #include <cstring> #define pb push_back #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int maxn = 1e5+5; vector<int> G[maxn]; int dfs_clock, iscut[maxn], pre[maxn], low[maxn]; int dfs(int u, int fa){ int lowu = pre[u] = ++dfs_clock; int child = 0; for(int i = 0; i < G[u].size(); i++){ int v = G[u][i]; ...