P2764 [网络流24题]最小路径覆盖问题[最大流]

这题有个转化，求最少的链覆盖→即求最少联通块。

设联通块个数$x$个,选的边数$y$,点数$n$个

那么有 $y=n-x$ 即 $x=n-y$

而n是不变的,目标就是在保证每个点入度、出度不大于1的前提下让选的边尽可能地多。

下面网络流建模。

利用二分图匹配建图，左右两点集都包含 n 个点，左点集代表 u 的出度，右点集代表 u 的入度。对于原图中的边 (u,v)，从左边的u点向右边的v点连一条容量为 1 的边，左点集与超级源点、右点集与超级汇点都分别连一条容量 1 的边，然后从源点做最大流，容量设1保证了我们每个点只流向另外唯一一个点，不会重叠。最大流即为所选边在满足条件下的最多数量。答案就是$n-y$。

spj那个的话就只要找到每一块的起点，也就是入度为0，这个看代码。找到起点就往后查残量为0的边顺着跑到底就行啦。

注意，这个只能是对DAP有效。有环的话就不行了，连通块会多余边会被流过，可以画一下。

 #include<bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> pii;

 template<typename T>inline char MIN(T&A,T B){return A<B?A=B,:;}

 template<typename T>inline char MAX(T&A,T B){return A>B?A=B,:;}

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline T read(T&x){

     x=;char c;while(!isdigit(c=getchar()))if(isalpha(c))return x=(int)c;

     while(isdigit(c))x=(x<<)+(x<<)+(c^),c=getchar();return x;

 }

 const int N=+,M=+,INF=0x3f3f3f3f;

 int w[M<<],v[M<<],Next[M<<],Head[N<<],cur[N<<],dis[N<<],tot=,s,t,n,m;

 inline void Addedge(int x,int y,int z){

     v[++tot]=y,Next[tot]=Head[x],Head[x]=tot,w[tot]=z;

     v[++tot]=x,Next[tot]=Head[y],Head[y]=tot,w[tot]=;

 }

 #define y v[j]

 inline char bfs(){

     queue<int> q;q.push(s),memset(dis,,sizeof dis),dis[s]=;

     for(register int i=;i<=(n<<)+;++i)cur[i]=Head[i];

     while(!q.empty()){

         int x=q.front();q.pop();

         for(register int j=Head[x];j;j=Next[j])if(w[j]&&!dis[y]){

             dis[y]=dis[x]+,q.push(y);

             if(y==t)return ;

         }

     }

     return ;

 }

 int dinic(int x,int flow){

     if(!flow||x==t)return flow;

     int rest=flow,k;

     for(register int j=cur[x];j&&rest;cur[x]=j,j=Next[j])if(w[j]&&dis[y]==dis[x]+){

         if(!(k=dinic(y,_min(rest,w[j]))))dis[y]=;

         rest-=k,w[j]-=k,w[j^]+=k;

     }

     return flow-rest;

 }

 #undef y

 int x,y,ans;

 inline void print(int x){

     printf("%d ",x);

     for(register int j=Head[x];j;j=Next[j])if(v[j]<s&&!w[j])print(v[j]-n);

 }

 int main(){//freopen("tmp.in","r",stdin);freopen("tmp.out","w",stdout);

     read(n),read(m);s=*n+,t=*n+;

     for(register int i=;i<=n;++i)Addedge(s,i,);

     for(register int i=n+;i<=n*;++i)Addedge(i,t,);

     for(register int i=;i<=m;++i)read(x),read(y),Addedge(x,y+n,);

     while(bfs())ans+=dinic(s,INF); ans=n-ans;

     for(register int i=n+;i<s;++i){//  s <==> n*2+1

         int tmp=;

         for(register int j=Head[i];j;j=Next[j])if(v[j]<=n&&w[j]){tmp=;break;}

         if(!tmp)print(i-n),puts("");

     }

     printf("%d\n",ans);

     return ;

 }

巴特西

P2764 [网络流24题]最小路径覆盖问题[最大流]

最新文章

热门文章