題目鏈接：點擊查看
題目大意：給出 n 個節點，再給出 n 個出邊，保證所有的邊能將 n 個點連通，每條出邊可以用 m[ i ] 種材料選擇其一建造，然后有 k 個工人，每個工人只可以使用一種材料建造一條邊，問是否可以通過合理的分配工人，使得整張圖連通
題目分析：n 個點，n 條邊組成的連通圖，換句話說就是一棵樹上加了一條邊，再換句話說這就是一棵基環樹，而每條邊對應的材料以及每個工人可以進行的匹配，不難想到用最大流來實現，但是并不能單純的跑最大流，因為有些條件的限制，比如 n 條邊并不需要全部選擇
所以我們需要考慮，n 條邊該如何進行選擇，因為整棵樹是一個基環樹，存在著恰好一個環，我們用 dfs 維護一個棧不難將這個環找出來，這樣整棵樹上的 n 條邊就劃分為了兩類，分別是環邊和樹邊，很顯然的一點就是，樹邊最后一定是全部需要選擇的，而至多有一個環邊不被選擇
同時工人也并不需要全部工作，因為題目要求的是，只需要在工人工作后，使得整棵樹連通即可，所以工人和樹邊都存在著選與不選兩種狀態
到此為止我們就轉換為有源匯有上下界的最大流的問題了，簡單建一下圖：
建好圖后直接跑模板就好了，關于路徑輸出也是簡單寫個 for 套上個 if 隨便寫寫就好了
需要注意的點是：實現時我并沒有將邊映射到點上，而是直接維護的每條邊，因為感覺這樣理解起來更簡單一些，其中的映射關系我用到了 map ，同理我也沒有將材料離散化，也是用 map 映射的
還有一個不知道算不算坑的坑點，我自己計算的邊數差不多是 1e5 級別的，所以第一次提交時將 M 設置為 1e6 ，結果在第五個測試點一直 RE，稍微 debug 了一會將 M 設置為 1e7 就順利通過了，可能是我這樣的實現會建更多的邊吧
代碼：
?
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e4+100;const int M=1e7+100;struct Edge1
{int u,v;bool circle;
}e[N];vector<int>node[N];map<int,vector<int>>color;map<pair<int,int>,int>mp;//邊映射為id int st[N],top;bool vis[N],flag;int du[N];//入度 struct Edge2
{int to,w,next;
}edge[M];//邊數int head[N],cnt;void addedge(int u,int v,int w)
{assert(cnt<M);edge[cnt].to=v;edge[cnt].w=w;edge[cnt].next=head[u];head[u]=cnt++;edge[cnt].to=u;edge[cnt].w=0;//反向邊邊權設置為0edge[cnt].next=head[v];head[v]=cnt++;
}void add(int u,int v,int lower,int upper)
{addedge(u,v,upper-lower);du[u]-=lower,du[v]+=lower;
}int d[N];//深度bool bfs(int s,int t)//尋找增廣路
{memset(d,0,sizeof(d));queue<int>q;q.push(s);d[s]=1;while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;int w=edge[i].w;if(d[v])continue;if(!w)continue;d[v]=d[u]+1;q.push(v);if(v==t)return true;}}return false;
}int dinic(int x,int t,int flow)//更新答案
{if(x==t)return flow;int rest=flow,i;for(i=head[x];i!=-1&&rest;i=edge[i].next){int v=edge[i].to;int w=edge[i].w;if(w&&d[v]==d[x]+1){int k=dinic(v,t,min(rest,w));if(!k)d[v]=0;edge[i].w-=k;edge[i^1].w+=k;rest-=k;}}return flow-rest;
}void init()
{memset(du,0,sizeof(du));memset(head,-1,sizeof(head));cnt=0;
}int solve(int st,int ed)
{int ans=0,flow;while(bfs(st,ed))while(flow=dinic(st,ed,inf))ans+=flow;return ans;
}void mark_circle(int u,int v)
{pair<int,int>t(u,v);if(t.first>t.second)swap(t.first,t.second);e[mp[t]].circle=true;
}void dfs(int u,int fa)
{st[++top]=u;vis[u]=true;for(auto v:node[u]){if(v==fa)continue;if(vis[v]){int temp=st[top];mark_circle(v,temp);while(temp!=v&&top){top--;mark_circle(temp,st[top]);temp=st[top];}flag=true;return;}dfs(v,u);if(flag)return;}top--;
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);init();int n,k;scanf("%d%d",&n,&k);int st=N-1,ed=st-1;int s=n+k+1,t=s+1;for(int i=1;i<=n;i++){int x;scanf("%d",&x);node[x].push_back(i);node[i].push_back(x);e[i].u=i,e[i].v=x;if(e[i].u>e[i].v)//滿足u<=v swap(e[i].u,e[i].v);mp[make_pair(e[i].u,e[i].v)]=i;int num;scanf("%d",&num);while(num--){int c;scanf("%d",&c);color[c].push_back(i);}}dfs(1,-1);//基環樹找環for(int i=1;i<=n;i++){if(e[i].circle)//環邊 add(i+k,t,0,1);else//樹邊 add(i+k,t,1,1);}for(int i=1;i<=k;i++)//工人 {int c;scanf("%d",&c);add(s,i,0,1);for(int num:color[c])add(i,num+k,0,1);}int sum=0;for(int i=1;i<=n+k+2;i++){if(du[i]>0){addedge(st,i,du[i]);sum+=du[i];}elseaddedge(i,ed,-du[i]);}addedge(t,s,inf);if(solve(st,ed)!=sum)return 0*puts("-1");int ans=edge[cnt-1].w;edge[cnt-1].w=edge[cnt-2].w=0;ans+=solve(s,t);if(ans<n-1)return 0*puts("-1");for(int i=1;i<=k;i++)//枚舉工人{for(int j=head[i];j!=-1;j=edge[j].next){int pos=edge[j].to;if(pos>k&&pos<=k+n&&edge[j^1].w==1){printf("%d %d\n",e[pos-k].u,e[pos-k].v);goto end;}}puts("0 0");end:;}return 0;
}
?
總結
以上是生活随笔為你收集整理的CodeForces - 1252L Road Construction(基环树+有源汇有上下界的最大流)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
