bzoj 2718: [Violet 4] （floyed+匈牙利算法）

2718: [Violet 4]

Time Limit: 10 Sec   Memory Limit: 128 MB Submit: 484   Solved: 280 [ Submit][ Status][ Discuss]

Description

Input

Output

最多可选多少景点

Sample Input

7 6 1 2 2 3 5 4 4 3 3 6 6 7

Sample Output

2

HINT

Source

Ctsc2008 River & ural 1533. Fat Hobbits

[ Submit][ Status][ Discuss]  HOME   Back

题解：floyed+匈牙利算法

对于选定的一条路径来说，我们只能从这个路径中选取其中的一个点。

先用floyed求出每个点之间是否能相互到达，只要能相互到达就连边，然后对于新图跑最小路径覆盖。

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #define N 203 using namespace std; int n,m,f[N][N],tot; int point[N*2],nxt[N*N],v[N*N]; int vis[N*N],belong[N*2]; void add(int x,int y) { tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; } bool find(int x,int k) { for (int i=point[x];i;i=nxt[i]){ int j=v[i]; if (vis[j]==k) continue; vis[j]=k; if (find(belong[j],k)||!belong[j]) { belong[j]=x; return true; } } return false; } int main() { freopen("a.in","r",stdin); scanf("%d%d",&n,&m); for (int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); f[x][y]=1; } for (int k=1;k<=n;k++) for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (i!=j&&j!=k&&k!=i) if (f[i][k]&&f[k][j]) f[i][j]=1; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (f[i][j]) { add(i,j+n); } int size=0; for (int i=1;i<=n;i++) if (find(i,i)) size++; printf("%d\n",n-size); }