https://vjudge.net/problem/Kattis-planestrainsbutnotautomobiles

題意：給一個有向圖，火車可以由任意一個起點開始，每一個點只能經過一次，在坐火車的時候你可以選擇坐飛機到另外一個點，求坐飛機的最小次數，以及求出可能在哪里坐飛機和降落。

樣例：

?

思路：求坐飛機次數 就是裸的最小路徑覆蓋，然后bfs求出可能的起點和終點。

#include <iostream> #include <cstdio> #include <fstream> #include <algorithm> #include <cmath> #include <deque> #include <vector> #include <queue> #include <string> #include <cstring> #include <map> #include <stack> #include <set> #include <cstdlib> #include <list> #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson rt<<1 #define rson rt<<1|1 #define lowbit(a) ((a)&-(a)) #define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); #define fi first #define sc second #define pb push_back #define endl '\n' #define all(x) (x).begin(),(x).end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll> pii; int dx[8]= {-1,1,0,0,1,1,-1,-1},dy[8]= {0,0,1,-1,-1,1,-1,1}; const ll mod=998244353; const ll N =2e5+10; const ll M =250000; const double eps = 1e-4; //const double pi=acos(-1); ll re(){ll x;scanf("%lld",&x);return x;} ll qk(ll a,ll b){ll ans=1;while(b){if(b&1) ans=ans*a%mod;a=a*a%mod;b/=2;}return ans;} inline int read(){int sgn = 1; int sum = 0;char ch = getchar();while (ch < '0' || ch > '9') {if(ch == '-') sgn = -sgn;ch = getchar();}while ('0' <= ch && ch <= '9') {sum = sum*10+(ch-'0');ch = getchar();}return sgn*sum;}ll n,m; vector<int> g[N]; vector<int> a; int match[N]; int vis[N]; int vis1[N]; bool dfs(int x){for(int i:g[x]){if(!vis1[i]){vis1[i]=1;if(!match[i]||dfs(match[i])){match[x]=i;match[i]=x;return 1;}}}return 0; } void bfs(){FILL(vis,0);queue<int> q;for(int i=1;i<=n;i++){if(!match[i]) q.push(i);}while(!q.empty()){int u=q.front();q.pop();if(vis[u]) continue;vis[u]=1;a.pb(u);for(int v:g[u]){if(v!=match[u]&&match[v]){q.push(match[v]);}}}for(int i=n+1;i<=2*n;i++){if(!match[i]) q.push(i);}while(!q.empty()){int u=q.front();q.pop();if(vis[u]) continue;vis[u]=1;a.pb(u-n);//cout<<u-n<<endl;for(int v:g[u]){if(v!=match[u]&&match[v]){q.push(match[v]);}}}sort(all(a));a.erase(unique(all(a)),a.end()); } void sovle(){n=re(),m=re();for(int i=1;i<=m;i++){int u=re(),v=re();g[u].pb(v+n);g[v+n].pb(u);}ll ans=0;for(int i=1;i<=n;i++){FILL(vis1,0);if(dfs(i)) ans++;}bfs();cout<<n-ans-1<<endl;if(n-ans-1!=0)for(int i:a) cout<<i<<" "; }int main() {iosint t=1;while(t--){sovle();}return 0; }

總結

以上是生活随笔為你收集整理的Planes, Trains, but not Automobiles-求最小路径覆盖的起点终点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。