[SCOI2003]蜘蛛难题

Java 解法, 执行用时: 15ms, 内存消耗: 9540K, 提交时间: 2023-07-28 20:32:59

import java.io.*;
import java.math.*;
import java.util.*;

/*
 * Author: Atuer
 */

public class Main
{
	// ==== Solve Code ====//
	static int INF = 1000000010;

	public static void csh()
	{

	}

	public static void main(String[] args) throws IOException
	{
		csh();

		int t = 1;
		while (t-- > 0)
		{
			solve();
			out.flush();
		}

		out.close();
	}

	static int maxn = 25, maxm = 55;
	static int[] h = new int[maxn];
	// 长度 = 水能否满足往对应方向流的值
	static int[] nex = new int[maxm], des = new int[maxm], len = new int[maxm];
	static int idx = 1;

	public static void add(int a, int b, int c)
	{
		des[idx] = b;
		len[idx] = c;
		nex[idx] = h[a];
		h[a] = idx++;
	}

	public static void solve()
	{
		int n = in.nextInt();
		TreeMap<Integer, Integer> lsh = new TreeMap<>();
		int[] up = new int[n + 1], down = new int[n + 1];
		// 离散化存入所有桶的信息(up桶高,down水面)
		for (int i = 1; i <= n; i++)
		{
			lsh.put(in.nextInt(), i);
			up[i] = in.nextInt();
			down[i] = up[i] + in.nextInt();
		}

		int m = in.nextInt();
		for (int i = 1; i <= m; i++)
		{
			int x = in.nextInt();
			int y = in.nextInt();
			int d = in.nextInt();
			add(lsh.get(x - 1), lsh.get(x + d), y);
			add(lsh.get(x + d), lsh.get(x - 1), y);
		}

		int zx = in.nextInt();
		int zy = in.nextInt();
		int t = 0;
		s: while (true)
		{
			Queue<Integer> q = new LinkedList<Integer>();
			boolean[] can = new boolean[n + 1];
			can[1] = true;
			q.add(1);

			// 若该桶可流,则查找该桶可以流向的桶
			while (!q.isEmpty())
			{
				int p = q.poll();

				for (int j = h[p]; j != 0; j = nex[j])
				{
//					out.println(p + ">" + des[j] + ":" + len[j]);
					if (!can[des[j]] && down[p] <= len[j])
					{
						can[des[j]] = true;
						q.add(des[j]);
					}
				}

			}

			// 最低水面
			int max = 0;
			for (int i = 1; i <= n; i++)
				if (can[i])
					max = Math.max(down[i], max);

			// 蜘蛛能被淹到且可以被淹
			if (can[zx] && zy == max)
			{
				out.println(t);
				return;
			}

			// 水面溢出 (当前桶流通且水装满且是最低水面的桶)
			for (int i = 1; i <= n; i++)
				if (can[i] && down[i] == up[i] && down[i] == max)
					break s;

			// 查找最低水面
			for (int i = 1; i <= n; i++)
				if (can[i] && down[i] == max)
				{
					down[i]--;
					t++;
				}

//			out.println(t);
//			out.println(Arrays.toString(up));
//			out.println(Arrays.toString(down));

		}

		out.println(-1);
	}

	public static class Node implements Comparable<Node>
	{
		// last candrop
		int x, y;

		public Node(int x, int y)
		{
			this.x = x;
			this.y = y;
		}

		public String toString()
		{
			return this.x + " " + this.y;
		}

		@Override
		public int compareTo(Node o)
		{
			return (this.x + this.y) - (o.x + o.y);
		}

	}
	// ==== Solve Code ====//

	// ==== Template ==== //
	public static long cnm(int a, int b)
	{
		long sum = 1;
		int i = a, j = 1;
		while (j <= b)
		{
			sum = sum * i / j;
			i--;
			j++;
		}
		return sum;
	}

	public static int gcd(int a, int b)
	{
		return b == 0 ? a : gcd(b, a % b);
	}

	public static int lcm(int a, int b)
	{
		return (a * b) / gcd(a, b);
	}

	public static void gbSort(long[] a, int l, int r)
	{
		if (l < r)
		{
			int m = (l + r) >> 1;
			gbSort(a, l, m);
			gbSort(a, m + 1, r);

			long[] t = new long[r - l + 1];
			int idx = 0, i = l, j = m + 1;

			while (i <= m && j <= r)
				if (a[i] <= a[j])
					t[idx++] = a[i++];
				else
					t[idx++] = a[j++];

			while (i <= m)
				t[idx++] = a[i++];
			while (j <= r)
				t[idx++] = a[j++];

			for (int z = 0; z < t.length; z++)
				a[l + z] = t[z];
		}
	}
	// ==== Template ==== //

	// ==== IO ==== //
	static InputStream inputStream = System.in;
	static InputReader in = new InputReader(inputStream);
	static PrintWriter out = new PrintWriter(System.out);

	static class InputReader
	{
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream)
		{
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next()
		{
			while (tokenizer == null || !tokenizer.hasMoreTokens())
			{
				try
				{
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e)
				{
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		boolean hasNext()
		{
			while (tokenizer == null || !tokenizer.hasMoreTokens())
			{
				try
				{
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (Exception e)
				{
					return false;
					// TODO: handle exception
				}
			}
			return true;
		}

		public String nextLine()
		{
			String str = null;
			try
			{
				str = reader.readLine();
			} catch (IOException e)
			{
				e.printStackTrace();
			}
			return str;
		}

		public int nextInt()
		{
			return Integer.parseInt(next());
		}

		public long nextLong()
		{
			return Long.parseLong(next());
		}

		public Double nextDouble()
		{
			return Double.parseDouble(next());
		}

		public BigInteger nextBigInteger()
		{
			return new BigInteger(next());
		}

		public BigDecimal nextBigDecimal()
		{
			return new BigDecimal(next());
		}
	}
	// ==== IO ==== //
}

C++(clang++ 11.0.1) 解法, 执行用时: 3ms, 内存消耗: 424K, 提交时间: 2023-07-26 14:29:32

#include <bits/stdc++.h>
using namespace std;

int n,t,m;
struct node
{
	int x,y,h;
};
int sz[205];
int xx[205];
node a[205];
int lj[205][205];
bool vis[205];

struct edge
{
	int v,y;
};
vector<edge> e[205];


void solve()
{
	cin>>n;
	for(int i=1; i<=n; i++)
	{
		sz[i]=i;
		cin>>a[i].x>>a[i].y>>a[i].h;
		a[i].h=a[i].h+a[i].y;
		xx[a[i].x]=i;
	}
	cin>>m;
	for(int i=1; i<=m; i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		int u=xx[x-1];
		int v=xx[x+z];
		e[u].push_back({v,y});
		e[v].push_back({u,y});
	}
	int A,B;
	cin>>A>>B;
	vis[1]=true;
	int ans=0;
	while(1)
	{
		for(int i=1; i<=n; i++)
		{
			if(vis[i])
			{
				for(int j=0; j<e[i].size(); j++)
				{
					int v=e[i][j].v;
					int h=e[i][j].y;
//					cout<<i<<" "<<v<<" "<<h<<"\n";
					if(a[i].h<=h&&!vis[v])
					{
						vis[v]=true;
					}
				}
			}
		}
		int mn=0;
		for(int i=1; i<=n; i++)
		{
			if(vis[i])
			{
				mn=max(mn,a[i].h);
			}
		}
		if(vis[A]&&mn==B)
		{
			cout<<ans<<"\n";
			return;
		}
		for(int i=1; i<=n; i++)
		{
			if(vis[i]&&a[i].h==a[i].y&&a[i].y==mn)
			{
				cout<<"-1\n";
				return;
			}
		}
		for(int i=1; i<=n; i++)
		{
			if(vis[i]&&a[i].h==mn)
			{
				a[i].h--;
				ans++;
//				cout<<i<<" "<<ans<<" "<<mn<<"\n";
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int cnt=0;
	int tn=1;
	while(tn--)
	{
		solve();
	}
}

详情