题意：给出一个折线图，有N条线段，你想要把这些线段分成几个集合，使得每个集合中任意两条线段不相交
题解：
最小路径覆盖
把每条线段当成一个点，若两条线段不相交则连一条边，则问题可转化为用最少的路径数使所有点都被经过，即为最小路径覆盖
最小路径覆盖=N-二分图最大匹配
注意：连边只能往一个方向连，即表示出两点的连通性即可
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<cstring> 5 #include<algorithm> 6 #include<cmath> 7 #define ll long long 8 using namespace std; 9 10 const int N = 110; 11 12 int T,n,m,ans,tot; 13 int a[N],b[N],dfn[N],s[N][30],g[N][N]; 14 bool vis[N]; 15 16 int gi() { 17 int x=0,o=1; char ch=getchar(); 18 while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar(); 19 if(ch=='-') o=-1,ch=getchar(); 20 while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); 21 return o*x; 22 } 23 24 void init() { 25 ans=0; 26 memset(s,0,sizeof(s)); 27 memset(g,0,sizeof(g)); 28 memset(a,-1,sizeof(a)); 29 memset(b,-1,sizeof(b)); 30 } 31 32 bool cmp(const int &x, const int &y) { 33 return s[x][0]<s[y][0]; 34 } 35 36 bool check(int u, int v) { 37 for(int i=1; i<=m; i++) { 38 if(s[u][i]>=s[v][i]) return false; 39 } 40 return true; 41 } 42 43 bool dfs(int u) { 44 for(int i=1; i<=n; i++) { 45 if(g[u][i] && !vis[i]) { 46 vis[i]=1; 47 if(dfs(b[i]) || b[i]==-1) { 48 b[i]=u,a[u]=i; 49 return true; 50 } 51 } 52 } 53 return false; 54 } 55 56 int main() { 57 T=gi(); 58 while(T--) { 59 init(); 60 n=gi(),m=gi(); 61 for(int i=1; i<=n; i++) 62 for(int j=1; j<=m; j++) { 63 s[i][j]=gi(); 64 s[i][0]=max(s[i][0],s[i][j]); 65 } 66 for(int i=1; i<=n; i++) dfn[i]=i; 67 sort(dfn+1,dfn+n+1,cmp); 68 for(int i=1; i<=n; i++) { 69 int u=dfn[i],v; 70 for(int j=i+1; j<=n; j++) { 71 v=dfn[j]; 72 if(check(u,v)) g[u][v]=1; 73 } 74 } 75 for(int i=1; i<=n; i++) { 76 if(a[i]==-1) { 77 memset(vis,0,sizeof(vis)); 78 if(dfs(i)) ans++; 79 } 80 } 81 printf("Case #%d: %d ", ++tot,n-ans); 82 } 83 return 0; 84 }