将一个点划分成两个, 对于边 u->v, 连边 ui -> vj , 这是个二分图求最大流, 答案 = 顶点数 - 最大流.
考前复习模型, 不求甚解.
代码都是半个月前的.
- // q.c
- // 数组开小调 0.5h.
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<cmath>
- #include<queue>
- #define mem(a) memset(a,0,sizeof(a))
- using namespace std;
- const int M=150+10,INF=(int)1e9;
- struct Edge {
- int v,nex,flow,cap; Edge() {}
- Edge(int a,int b,int c,int d):v(a),nex(b),flow(c),cap(d) {}
- }ed[M*M<<1];
- int cnt,head[M<<1];
- void add_edge(int a,int b,int c) {
- ed[cnt]=Edge(b,head[a],0,c); head[a]=cnt++;
- ed[cnt]=Edge(a,head[b],0,0); head[b]=cnt++;
- }
- struct Dinic {
- int n,s,t,cur[M<<1],dis[M<<1]; queue<int> Q;
- Dinic():n(0),s(0),t(0) {
- mem(cur),mem(dis);
- while(!Q.empty()) Q.pop();
- }
- bool bfs() {
- mem(dis); dis[s]=1; Q.push(s);
- int u,i; Edge e;
- while(!Q.empty()) {
- u=Q.front(); Q.pop();
- for(i=head[u];i!=-1;i=ed[i].nex) {
- e=ed[i];
- if(!dis[e.v]&&e.cap>e.flow) {
- dis[e.v]=dis[u]+1;
- Q.push(e.v);
- }
- }
- }
- return dis[t];
- }
- int dfs(int u,int lim) {
- if(u==t||!lim) return lim;
- int f,tmp=0; Edge e;
- for(int &i=cur[u];i!=-1;i=ed[i].nex) {
- e=ed[i];
- if(dis[e.v]==dis[u]+1) {
- f=dfs(e.v,min(lim,e.cap-e.flow));
- if(f>0) {
- ed[i].flow+=f; tmp+=f;
- ed[i^1].flow-=f; lim-=f;
- if(!lim) break;
- }
- }
- }
- return tmp;
- }
- int solve(int x,int y,int z) {
- s=x; t=y; n=z; int ans=0;
- while(bfs()) {
- for(int i=0;i<=n;i++) cur[i]=head[i];
- ans+=dfs(s,INF);
- }
- return ans;
- }
- }DC;
- int n,m,ans,to[M],pre[M];
- void inputs() {
- scanf("%d%d",&n,&m); int a,b;
- for(int i=1;i<=n;i++) add_edge(0,i,1);
- for(int i=1;i<=n;i++) add_edge(i+n,2*n+1,1);
- for(int i=1;i<=m;i++) {
- scanf("%d%d",&a,&b);
- add_edge(a,b+n,1);
- }
- ans=DC.solve(0,2*n+1,2*n+1);
- }
- void prints() {
- for(int i=1;i<=n;i++) for(int j=head[i];j!=-1;j=ed[j].nex) {
- Edge e=ed[j];
- if(e.flow==1) {
- to[i]=e.v-n; pre[e.v-n]=i;
- break;
- }
- }
- for(int i=1,j=0;i<=n;i++) if(!pre[i]) {
- j=i;
- while(j) printf("%d",j),j=to[j];
- printf("\n");
- }
- printf("%d\n",n-ans);
- }
- int main() {
- freopen("path3.in","r",stdin);
- freopen("path3.out","w",stdout);
- memset(head,-1,sizeof(head));
- inputs();
- prints();
- return 0;
- }
[网络流 24 题] 最小路径覆盖问题
来源: http://www.bubuko.com/infodetail-2570199.html