题目

如题

分析

第一问很简单， \(dp\) 即可（得先排序）

第二问很经典，最小路径覆盖问题，最大流解决 \(n-Maxflow\)

\(Code\)

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<queue>

using namespace std;

const int N = 1005;

int n , f[N] , tot = 1 , dep[2 * N] , cur[2 * N] , h[2 * N] , S = 0 , T = 2 * N - 9;

struct node{

	int x , y , z;

}a[N];

struct edge{

	int to , nxt , w;

}e[2 * N * N];

bool cmp(node x , node y)

{

	return (x.x < y.x ? 1 : (x.x == y.x ? (x.y < y.y ? 1 : (x.y == y.y ? x.z < y.z : 0)) : 0));

}

inline void add(int x , int y , int z){e[++tot] = edge{y , h[x] , z} , h[x] = tot;}

queue<int> q;

int bfs()

{

	while (!q.empty()) q.pop();

	for(register int i = S; i <= T; i++) cur[i] = h[i] , dep[i] = 0;

	dep[S] = 1 , q.push(S);

	while (!q.empty())

	{

		int now = q.front(); q.pop();

		for(register int i = h[now]; i; i = e[i].nxt)

		{

			int v = e[i].to;

			if (dep[v] || e[i].w == 0) continue;

			dep[v] = dep[now] + 1 , q.push(v);

		}

	}

	return dep[T];

}

int dfs(int x , int fa , int mi)

{

	if (x == T || mi <= 0) return mi;

	int flow = 0;

	for(register int i = cur[x]; i; i = e[i].nxt)

	{

		cur[x] = i;

		int v = e[i].to;

		if (e[i].w == 0 || v == fa || dep[x] + 1 != dep[v]) continue;

		int f = dfs(v , x , min(mi , e[i].w));

		if (f <= 0) continue;

		flow += f , mi -= f , e[i].w -= f , e[i ^ 1].w += f;

		if (mi <= 0) break;

	}

	return flow;

}

int dinic()

{

	int flow = 0;

	while (bfs()) flow += dfs(S , -1 , n);

	return flow;

}

int main()

{

	freopen("missile.in" , "r" , stdin);

	freopen("missile.out" , "w" , stdout);

	scanf("%d" , &n);

	for(register int i = 1; i <= n; i++) scanf("%d%d%d" , &a[i].x , &a[i].y , &a[i].z);

	sort(a + 1 , a + n + 1 , cmp);

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

	{

		f[i] = 1;

		for(register int j = 1; j < i; j++)

		if (a[j].x < a[i].x && a[j].y < a[i].y && a[j].z < a[i].z && f[j] + 1 > f[i]) f[i] = f[j] + 1;

	}

	int ans = 0;

	for(register int i = 1; i <= n; i++) ans = max(ans , f[i]);

	printf("%d\n" , ans);

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

		add(S , i , 1) , add(i , S , 0) , add(i + n , T , 1) , add(T , i + n , 0);

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

		for(register int j = 1; j <= n; j++)

		if (i != j && a[j].x > a[i].x && a[j].y > a[i].y && a[j].z > a[i].z)

			add(i , j + n , 1) , add(j + n , i , 0);

	printf("%d" , n - dinic());

}

巴特西

JZOJ 5354. 【NOIP2017提高A组模拟9.9】导弹拦截

题目

分析

\(Code\)

最新文章

热门文章