「网络流 24 题」深海机器人问题题解:我们拆边
「网络流 24 题」汽车加油行驶问题题解:对于一个点如果是没有加油站,就有设置加油站或者是直接走,通过调整方向函数将向回走的放在前面,然后就可以收费。#include <bits/stdc++.h> const int MAXN = 105,INF = 10000000; const int fx[] = {-1,0,1,0},fy[] = {0,-1,0,1}; using...
「网络流 24 题」航空路线问题题解:求两条最大权不相交路径,用map将城市string映射到城市编号i,然后将每个城市i拆成Xi和Yi并且连接一条容量为1,权值为0的边,然后从源点向第一个点连接容量为1,权值为0的边,输出好麻烦啊!#include <bits/stdc++.h> const int MAXN = 1000000,INF = 10000000; using ...
「网络流 24 题」孤岛营救问题题解:建立分层图每一层用二进制状态表示拥有的钥匙。跑spfa就好了#include <bits/stdc++.h> const int fx[] = {1,-1,0,0},fy[] = {0,0,1,-1},INF = 1000000; using namespace std; int n,m,p,k,s,ans; int door[15][...
「网络流 24 题」星际转移题解:本题的难点在于问题中涉及到很多天,而对于这种涉及到很多天的问题我们一般用分层图的实现来解决。对于每一天建一层图,然后对于每个飞行器就从前一天向后一天的位置连边容量为飞船容量的边,然后对于每个点从前一天向后一天连边。枚举天数,当最大流大于总人数的时候输出天数#include <bits/stdc++.h> #define pb push_back ...