找了一整天错误了,找不到,哭死T T
查看原帖
找了一整天错误了,找不到,哭死T T
638969
kkkj楼主2023/5/26 16:48
import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		init();
		long cnt = 0;
		while(bfs()) {
			cnt += dfs(s, Integer.MAX_VALUE/2);
		}
		System.out.println(cnt);
	}
	static int s, e, N;
	static int index = 2;
	static int[] start, dest, dis, next;
	static void add(int a, int b) {
		add_edge(a, b);
		add_edge(b, a);
	}
	static void add_edge(int a, int b) {
		next[index] = start[a];
		start[a] = index;
		dest[index] = b;
		dis[index] = 1;
		index++;
	}
	static void init() throws IOException {
		int N1 = nextInt();
		int N2 = nextInt();
		int N3 = nextInt();
		N = 1000000;
		
		record = new int[N];
		start = new int[N];
		dest = new int[N];
		dis = new int[N];
		next = new int[N];
		
		
		
		s = 0;
		e = N1*2+N2+N3+1	;
		//System.out.println(s+" "+e);
		
		int M1 = nextInt();
		for (int i = 0; i < M1; i++) {
			int book = nextInt();
			int id = N1*2 + nextInt();

			add(id, book);
		}

		int M2 = nextInt();
		for (int i = 0; i < M2; i++) {
			int book = nextInt() + N1;
			int id = N1*2 + N2 + nextInt();
			
			add(book, id);
		}
		
		for (int i = 1; i <= N1; i++)
			add(i, i+N1);
		
		for (int i = 1; i <= N2; i++)
			add(s, N1*2 + i);
		
		for (int i = 1; i <= N3; i++)
			add(e, N1*2+N2 + i);
		
	}
	
	
	
	static ArrayList<Integer> path = new ArrayList<Integer>();
	static int[] deep, record;
	static boolean bfs() {
		deep = new int[N];
		deep[s] = 1;
		Queue<Integer> que = new LinkedList<Integer>();
		que.add(s);
		while(!que.isEmpty()) {
			int now = que.poll();
			record[now] = start[now];
			for (int i = start[now]; i != 0; i = next[i]) {
				int b = dest[i];
				int d = dis[i];
				if(deep[b]==0 && d>0) {
					que.add(b);
					deep[b] = deep[now]+1;
				}
			}
		}
		return deep[e] > 0;
	}
	
	
	static int dfs(int now, int val) {
		path.add(now);
		if(now == e) {
			for (int i = 0; i < path.size(); i++) {
				System.out.print(path.get(i)+"  ");
			}
			System.out.println();
			path.remove(path.size()-1);
			return val;
		}
		if(now == e) return val;
		int rem = val;
		for (int i = record[now]; i != 0; i = next[i]) {
			record[now] = i;
			int b = dest[i];
			int d = dis[i];
			if(deep[b] == deep[now]+1 && d>0) {
				int min = Math.min(d, rem);
				int use = dfs(b, min);
				dis[i] 	 -= use;
				dis[i^1] += use;
				rem -= use;
				if(rem <= 0)
					break;
			}
		}
		path.remove(path.size()-1);
		return val - rem;
	}
	
	
	
	
	
	
	
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StreamTokenizer st = new StreamTokenizer(br);
	static int nextInt() throws IOException {
		st.nextToken();
		return (int)st.nval;
	}
	
	
	
	
}

2023/5/26 16:48
加载中...