2019-2020 ICPC, Asia Jakarta L - Road Construction 网络流

直接用城市建点的话不好表达连边的关系

考虑把每条边看作左部点

右部点的话朴素想法是工人，但是也不好表达工人和材料的关系

发现工人的信息可以整合成一共有多少种材料，每种材料有多少人擅长

所以把材料看成右部点，城市和所需材料之间连容量为1的边，材料和汇点T之间连容量为“擅长该材料人数”的边

那基环树怎么处理？一共只有n条边..要让图联通

考虑到有解的话，不在环上的边一定要选，在环上的边有一条可以不选

假设边u不在环上，源点s向u连一条容量为1的边表示选取

假设边u在环上，新建一个超级源点s1，s1向u连一条容量为1的边，s向s1连容量为1的边

到此，跑一个最大流，如果解>=n-1的话说明我们可以通过选取n-1条边使得图联通

输出路径的话，从T出发，遍历所有边，然后只走流过的边，来到右部点。

再从右部点出发，只走有流过的边，来到左部点，能走到表示该边需要被连接，打个记号再记一下用了什么材料就可以。

哦对了递归的话不要调用stl自带的栈，不然会re得很惨:)

#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
const int maxn=3e5+5;
struct lys{
    ll from,to,nxt,c;
}e[maxn*6];
ll cnt=1,s,s1,t,dep[maxn<<1],head[maxn<<1];
ll val[maxn*6];// val && edge 
void add(ll from,ll to,ll c)
{
    cnt++;
    e[cnt].from=from;e[cnt].to=to;e[cnt].nxt=head[from];head[from]=cnt;val[cnt]=c;
}

bool  bfs()
{   queue<int>q;
    memset(dep,0,sizeof(dep));
    q.push(s);
    dep[s]=1;
    while(!q.empty())
    {
        ll u=q.front();
        q.pop();
        for(ll i=head[u];i;i=e[i].nxt)
        {
            ll to=e[i].to;
            if(val[i]&&!dep[to])
            {
                dep[to]=dep[u]+1;
                q.push(to);
            }
        }
    }
    return dep[t];    
    // dep[t]!=0  say that t can be reached 
}
ll dfs(int u,ll in)
{
    if(u==t) 
    return in;
    ll out=0;
    for(ll i=head[u];i&&in;i=e[i].nxt)
    {
      int to=e[i].to;
      if(val[i]&&dep[to]==dep[u]+1)
      {
          ll res=dfs(to,min(val[i],in));
          val[i]-=res;// val :e[i].c-e[i].f, i..e left network 
          val[i^1]+=res;
          in-=res;
          out+=res;
      }    
    }
    
    if(!out) 
      dep[u]=0;
    return out;
}
ll dinic(){
    ll ans=0;
    while(bfs())     
    ans+=dfs(s,1e18);
//    cout<<"#max flow："<<ans<<endl;
    return ans;
}
bool vis[maxn<<1];
map<int,int>mp,tot;
int good[maxn],work[maxn],tmpk,a[maxn],m[maxn],k,n,len=0;
set<int>c[maxn];
bool tag[maxn];
vector<pair<int,int>>r[maxn];
int top1=0,top2=0;
int sta[maxn],Esta[maxn];
void findCycle(int u,int from){
    if(len!=0) return;
    vis[u]=1;
    sta[++top1]=u;
    Esta[++top2]=from;
    for(int i=0;i<r[u].size()&&!len;i++){
        int to=r[u][i].first;
        int id=r[u][i].second;
        if(id==from) continue;
        if(!vis[to]) findCycle(to,id);
        else {
            int p,q;
            do{
                p=sta[top1];top1--;
                q=Esta[top2];top2--;
                //cout<<p<<" cycle "<<q<<" "<<endl;
                if(p!=to) tag[q]=1,len++;
            }while(p!=to&&top1);
            tag[id]=1;
            len++;
            //cout<<len<<" "<<id<<endl;
            return;
        }
    }
    top1--;
    top2--;
}
int use[maxn],_from[maxn],_to[maxn];
int main()
{   //freopen("lys.in","r",stdin);
    fastio;
    cin>>n>>k;
    tmpk=k;
    int materi=n;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>m[i];
        r[i].push_back({a[i],i});
        r[a[i]].push_back({i,i});
        for(int j=1;j<=m[i];j++){
            int b;cin>>b;
            if(!mp[b]) mp[b]=++materi;
            c[i].insert(mp[b]);
        }
    }
    map<int,int>tot;
    for(int i=1;i<=k;i++){
        cin>>good[i];
        if(!mp[good[i]]) mp[good[i]]=++materi;
        good[i]=mp[good[i]];
        work[i]=good[i];
        tot[good[i]]++;
    }
    sort(good+1,good+1+k);
    k=unique(good+1,good+1+k)-good-1;
    
    s=0;s1=materi+1;t=materi+2;
    // 1-n city n+1-n+cnt material 
    // 0,s  n+cnt+1,s1 n+cnt+2,t
    
    // edges and materials
    for(int i=1;i<=n;i++){
        for(auto x:c[i]){
            add(i,x,1);
            add(x,i,0);
            //cout<<i<<" material "<<x<<endl;
        }
    }
    // materials and t ,val==works
    for(int i=1;i<=k;i++){
    //    cout<<good[i]<<" "<<t<<" "<<tot[good[i]]<<endl;
        add(good[i],t,tot[good[i]]);
        add(t,good[i],0);
    }
    
    findCycle(1,0);

    for(int i=1;i<=n;i++){
        if(!tag[i]){
            //cout<<"type1 "<<s<<" "<<i<<endl;
            add(s,i,1);
            add(i,s,0);
        }
        else {
            //cout<<"type2 "<<s1<<" "<<i<<endl;
            add(s1,i,1);
            add(i,s,0);
        }
    }
    //cout<<"len "<<len<<endl;
    add(s,s1,len-1);
    add(s1,s,0);
    
    ll myAns=dinic();
    // find min point cover
    if(myAns<n-1){
        return cout<<"-1",0;
    }
    //cout<<myAns<<endl;
    for(int i=head[t];i;i=e[i].nxt){
        int to=e[i].to;
        if(val[i]!=0){
            for(int j=head[to];j;j=e[j].nxt){
                int go=e[j].to;
                if(val[j]!=0)
                  use[go]=to;
            }  
        }
    }
    for(int i=1;i<=n;i++){
        if(!use[i]) continue;
        for(int j=1;j<=tmpk;j++){
            if(work[j]==use[i]&&_from[j]==0&&_to[j]==0){
                _from[j]=i;
                _to[j]=a[i];
                break;
            }
        }
    }
    for(int i=1;i<=tmpk;i++){
        cout<<_from[i]<<" "<<_to[i]<<endl;
    }
}