本文共 1726 字，大约阅读时间需要 5 分钟。
题意：有水平N张牌，竖直M张牌，同一方向的牌不会相交。水平的和垂直的可能会相交，求最少踢出去几张牌使剩下的牌都不相交。
二分匹配 最小点覆盖=最大匹配。
链接：
坐标点作为匹配的端点
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 #define MOD 1000000007 10 const int INF=0x3f3f3f3f; 11 const double eps=1e-5; 12 typedef long long ll; 13 #define cl(a) memset(a,0,sizeof(a)) 14 #define ts printf("*****\n"); 15 int n,m,tt; 16 /* 17 * 匈牙利算法邻接表形式 18 * 使用前用init()进行初始化，给uN赋值 19 * 加边使用函数addedge(u,v) 20 * 21 */ 22 const int MAXN = 2505;//点数的最大值 23 const int MAXM = 50010;//边数的最大值 24 struct Edge 25 { 26 int to,next; 27 }edge[MAXM]; 28 int head[MAXN],tot; 29 void init() 30 { 31 tot = 0; 32 memset(head,-1,sizeof(head)); 33 } 34 void addedge(int u,int v) 35 { 36 edge[tot].to = v; edge[tot].next = head[u]; 37 head[u] = tot++; 38 } 39 int linker[MAXN]; 40 bool used[MAXN]; 41 int uN; 42 bool dfs(int u) 43 { 44 for(int i = head[u]; i != -1 ;i = edge[i].next) 45 { 46 int v = edge[i].to; 47 if(!used[v]) 48 { 49 used[v] = true; 50 if(linker[v] == -1 || dfs(linker[v])) 51 { 52 linker[v] = u; 53 return true; 54 } 55 } 56 } 57 return false; 58 } 59 int hungary() 60 { 61 int res = 0; 62 memset(linker,-1,sizeof(linker)); 63 for(int u = 0; u < uN;u++)//点的编号0~uN-1 64 { 65 memset(used,false,sizeof(used)); 66 if(dfs(u))res++; 67 } 68 return res; 69 } 70 pair p1[MAXN]; 71 pair p2[MAXN]; 72 int main() 73 { 74 int i,j,k; 75 #ifndef ONLINE_JUDGE 76 freopen("1.in","r",stdin); 77 #endif 78 while(scanf("%d%d",&n,&m)!=EOF) 79 { 80 if(n==0&&m==0) break; 81 init(); 82 int x,y; 83 for(i=0;i
转载于:https://www.cnblogs.com/cnblogs321114287/p/4617119.html