题意：

给出了男女之间的暧昧关系..求解有多少人之间是没有暧昧关系的..

先给n表示有n个同学

然后 同学a:(暧昧关系人数m) 暧昧关系同学1 暧昧关系同学2 暧昧同学3 ... 

思路：

求出最大独立集..

 

Tips：

有向图：最大独立集 = n-最大匹配

无向图：最大独立集 = n-最大匹配/2

Code：

1 #include 
      
        2 #include 
       
         3 #define clr(x) memset(x, 0, sizeof(x)) 4 const int INF = 0x1f1f1f1f; 5  6 struct Edge 7 { 8     int next; 9     int to;10 }edge[1000000];11 int tot;12 int head[510];13 14 void add(int s, int u)15 {16     edge[tot].to = u;17     edge[tot].next = head[s];18     head[s] = tot++;19 }20 21 int link[510];22 int vis[510];23 int sum, n;24 25 int dfs(int x)26 {27     for(int i = head[x]; i != -1; i = edge[i].next){28         int y = edge[i].to;29         if(!vis[y]){30             vis[y] = true;31             if(link[y] == 0 || dfs(link[y])){32                 link[y] = x;33                 return true;34             }35         }36     }37     return false;38 }39 40 void solve()41 {42     clr(link);43     sum = 0;44     for(int i = 0; i < n; ++i){45         clr(vis);46         if(dfs(i))47             sum++;48     }49 }50 51 int main()52 {53     int i, j, k;54     int a, b, m;55     while(scanf("%d", &n) != EOF)56     {57         memset(head, 0xff, sizeof(head));58         for(i = 0; i < n; ++i) {59             scanf("%d: (%d)", &a, &m);60             while(m--) {61                 scanf("%d", &b);62                 add(a, b);63             }64         }65 66         solve();67 68         printf("%d\n", n-sum/2);69     }70     return 0;71 }