Sessions in BSU

有n项考试。每项考试给定两个时间，你可以任意选择一个时间。每个时间点只能考一场考试，请问在最优情况下最早考完的时间。n<=1e6。

把题目抽象成图论模型：在每项考试的两个时间点之间连边，那么问题就变成了：给所有边定向，使得每个时间点的入度至多为1，请你让入度为1的点的编号的最大值最小。

然后，我们可以发现只有基环树和树是合法的。对于基环树，取最大值；对于树，去最小值，然后对所有值取max就行了。

exp：如果在代码里用全局变量的话，就不用写两个dfs了。所以说别忘记在dfs之前想想返回值能不能用全局变量记录！也想想能不能用引用来记录。

#include <map>

#include <cstdio>

#include <algorithm>

using namespace std;

typedef pair<int, int> pi;

const int maxn=2e6+5;

int n, a, b, ans;

struct Edge{

	int to, nxt;

}e[maxn*2];

int cntedge, fir[maxn];

void addedge(int x, int y){

	Edge &ed=e[++cntedge];

	ed.to=y; ed.nxt=fir[x]; fir[x]=cntedge;

}

int vis[maxn], cnte, cntn;

void dfs(int now){

	++cntn; vis[now]=1;

	for (int i=fir[now]; i; i=e[i].nxt){

		++cnte;

		if (!vis[e[i].to]) dfs(e[i].to);

	}

}

int vis2[maxn];

pi dfs2(int now){

	if (vis2[now]) return make_pair(0, 0);

	pi re=make_pair(now, 0), tmp;

	vis2[now]=1;

	for (int i=fir[now]; i; i=e[i].nxt){

		tmp=dfs2(e[i].to);

		if (tmp.first>re.first){

			re.second=re.first;

			re.first=tmp.first;

		} else if (tmp.first>re.second)

			re.second=tmp.first;

		if (tmp.second>re.second) re.second=tmp.second;

	}

	return re;

}

int a1[maxn], a2[maxn], bb[maxn], mm, trans[maxn];

int main(){

	scanf("%d", &n); int x, y;

	for (int i=1; i<=n; ++i){

		scanf("%d %d", &a1[i], &a2[i]);

		bb[++mm]=a1[i]; bb[++mm]=a2[i]; }

	sort(bb+1, bb+mm+1); mm=unique(bb+1, bb+mm+1)-bb-1;

	for (int i=1; i<=n; ++i){

		x=lower_bound(bb+1, bb+mm+1, a1[i])-bb;

		y=lower_bound(bb+1, bb+mm+1, a2[i])-bb;

		addedge(x, y); addedge(y, x);

	}

	int ans=0; pi tmp;

	for (int i=1; i<=mm; ++i){

		if (vis[i]) continue;

		cntn=cnte=0; dfs(i); cnte/=2;

		if (cnte>cntn){ puts("-1"); return 0; }

		tmp=dfs2(i);

		if (cnte==cntn) ans=max(ans, tmp.first);

		else ans=max(ans, tmp.second);

	}

	printf("%d\n", bb[ans]);

	return 0;

}

巴特西

Sessions in BSU

Sessions in BSU

最新文章

热门文章