此題可以通過奇偶建立二分圖，將奇數點集令為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<
