Bzoj 1143
coc youyl
posted @ 2015年7月02日 16:20
in bzoj
, 877 阅读
题目链接:bzoj系列往后省略题目链接
题目分类:网络流
题意:
给出一个有向无环图,求他的最长反链。
题解:
根据Dilworth定理,偏序集的最长反链(最大独立集)=最小链覆盖(最小不相交路径覆盖)
所以先对原图进行一次传递闭包,然后拆点连边做最小不相交路径覆盖。
程序:
#include<cstdio> #include<queue> #include<algorithm> #include<cstring> #include<cstdlib> using namespace std; int st[3000],ed; struct node { int next,to,fl,opt; }g[4000000]; inline void add(int x,int y,int z) { // printf("%d %d %d\n",x,y,z); ed++; g[ed].to=y; g[ed].next=st[x]; g[ed].fl=z; g[ed].opt=ed+1; st[x]=ed; ed++; g[ed].to=x; g[ed].next=st[y]; g[ed].fl=0; g[ed].opt=ed-1; st[y]=ed; } int x1,x2,x3,lev[3000],des; inline bool makelev() { queue<int>q; q.push(0); memset(lev,0,sizeof(lev)); lev[0]=1; while (!q.empty()) { x1=q.front();q.pop(); for (int i=st[x1];i!=0;i=g[i].next) { if(lev[g[i].to]==0&&g[i].fl!=0) { q.push(g[i].to); lev[g[i].to]=lev[x1]+1; if(g[i].to==des)return true; } } }return false; } int stap,sta[3000],spre[3000],stae[3000]; int maxflow; inline void extend() { int del; stap=1; sta[1]=0; for (int i=0;i<=des;i++) { spre[i]=st[i]; } while (stap!=0) { x1=sta[stap]; // printf("%d\n",x1); if(x1!=des) { for (;spre[x1]!=0;spre[x1]=g[spre[x1]].next) { if(g[spre[x1]].fl!=0&&lev[x1]+1==lev[g[spre[x1]].to]) { break; } } if(spre[x1]!=0) { stap++; stae[stap]=spre[x1]; sta[stap]=g[spre[x1]].to; } else { stap--;lev[x1]=0; } } else { del=1000000000; for (int i=stap;i>=2;i--) { del=min(del,g[stae[i]].fl); } maxflow+=del; for (int i=stap;i>=2;i--) { g[stae[i]].fl-=del; g[g[stae[i]].opt].fl+=del; if(g[stae[i]].fl==0)stap=i-1; } } } } inline void dinic() { maxflow=0; while (makelev())extend();//,printf("%d\n",maxflow);; } int n,m,dp[1200][1200]; int main() { scanf("%d %d",&n,&m); des=n+n+1; for (int i=1;i<=n;i++) { add(0,i,1); add(i+n,des,1); } for (int i=1;i<=m;i++) { scanf("%d %d",&x1,&x2); dp[x1][x2]=1; } for (int k=1;k<=n;k++) { for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) { if(dp[i][k]==1&&dp[k][j]==1)dp[i][j]=1; } } } for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) { if(i!=j&&dp[i][j]==1) add(i,j+n,1); } } dinic(); printf("%d\n",n-maxflow); return 0; }