POJ3715【二分匹配-增广】-白红宇

POJ3715【二分匹配-增广】

阅读量：4984 次

发布时间：2019-06-12

本文共 639 字，大约阅读时间需要 2 分钟。

题意：

N个人，有两种人，M对亲密关系，问最少删除几个人达到没有亲密关系。

思路：

最大匹配 = 最小独立集，删掉该人对最大匹配数的影响，如果没有影响，删不删都无所谓，如果有影响贼删除；

类似HDU1281；

处理可用删除这个点以后找增广，如果找的到增广则无影响，找不到增广则有影响。

错误就是二分图，我要删的点有两种，两组点都有可能删除，*单方面删除了一种*。

错误在了无意识偏爱了一张图，其实二分图，两张图非常独立，地位平等且重要！

//#include
    
     //using namespace::std;//typedef pair
     
       PII;#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int N=2e2+10;bool ma[N][N];int cx[N],cy[N],n,m;bool vis[N],col[N],deleted[N];bool FindPateX(int u){ if(deleted[u]) return false; for(int i=0;i

转载于:https://www.cnblogs.com/keyboarder-zsq/p/6777455.html

你可能感兴趣的文章