hdu 1569 &1565 二分图带权最大独立集，最大流最小割定理

此题可以通过奇偶建立二分图，将奇数点集令为X集，偶数点集令为Y集。

二分图带权最大独立集：给出一个二分图，每个结点上有一个正权值。要求选出一些点，使得这些点之间没有边相连，且权值最大。（和题目所要求的一样）

所以我们可以将X集中与Y集中相邻的点连一条边，这样就构成了一个二分图。

用经典的建模方法

添加一个源点和X集相连，边容量为点权。

添加一个汇点与Y集相连，边容量为点权。

将X-Y原来的边的容量设为无穷大。

求出最小割，剩下的就是没有边相连的最大独立集，也就是答案。

而最大流=最小割。

dinic实现

#include
  
   
#include
   
     #include
    
      #include
     
       using namespace std; #define MAXN 2600 #define INF 0x3f3f3f3f #define isok(x,y) (x>=1&&x<=n&&y>=1&&y<=m) struct edge { int to,c,next; }; edge e[999999]; int que[MAXN*100]; int dis[MAXN]; int pre[MAXN]; int head[MAXN],head2[MAXN]; int st,ed; int maxflow; int en; int n,m; int id; int mp[55][55]; void add(int a,int b,int c) { e[en].to=b; e[en].c=c; e[en].next=head[a]; head[a]=en++; e[en].to=a; e[en].c=0; e[en].next=head[b]; head[b]=en++; } bool bfs() { memset(dis,-1,sizeof(dis)); que[0]=st,dis[st]=1; int t=1,f=0; while(f
      
       >n>>m) { init(); input(); build(); cout<