二分图详解

vector<int> G[maxn];  // 存边
int col[maxn];        // 标记顶点颜色
int n,m;         // 点和边的个数
 
bool bfs(){
  queue<int> q;
  q.push(1);     // 放入第一个点
  memset(col,0,sizeof(col));
  col[1] = 1;    // 先标记第一个点为1
  while(!q.empty()){
    int v = q.front();
    q.pop();
    for(int i=0;i<G[v].size();i++){
      int xx = G[v][i];
      if(col[xx] == 0){      // 判断这个点是否标记过
        col[xx] = -col[v];   // 没有标记过就标记上与v相反的颜色
        q.push(xx);
      }
      else{
        if(col[v] == col[xx]){    // 如果颜色冲突说明不是二分图
          return false;
        }
      }
    }
  }
  return true;
}

       对于匈牙利算法，之前我在学的时候发现了一篇讲解的很好的博客，具体的实现过程可以看一下这篇博客：https://blog.csdn.net/dark_scope/article/details/8880547，贴一个我的匈牙利呆码。

vector<int> G[maxn];    // 存边
int pre[maxn];     // 记录匹配点
bool vis[maxn];    // 标记是否匹配过
int n,m;           // n个点 m条边
 
bool dfs(int x){
  for(int i=0;i<G[x].size();i++){
    int v = G[x][i];
    if(vis[v] == false){       // 判断是否标记过
      vis[v] = true;
      if(pre[v] == -1 || dfs(pre[v])){      // 判断当前点是否匹配过 dfs为判断这个点能不能和其他的点匹配
        pre[v] = x;
        return true;
      }
    }
  }
  return false;
}
 
int Fun(){
  int sum = 0;
  memset(pre,-1,sizeof(pre));
  for(int i=1;i<=n;i++){
    memset(vis,false,sizeof(vis));     // 每次遍历都需要初始化
    if(dfs(i)) sum ++;
  }
  return sum;
}

#include <bits/stdc++.h>
#define maxn 3010
#define inf 0x3f3f3f3f
using namespace std;
struct Node{     int to,next;
}Edge[maxn*maxn];
struct node{     double x,y,v;
}a[maxn];
int head[maxn],num;
int lx[maxn],ly[maxn],dx[maxn],dy[maxn];
bool vis[maxn];
int T,n,m,t,dis;
 
void init(){     memset(lx,-1,sizeof(lx));     memset(ly,-1,sizeof(ly));     memset(head,-1,sizeof(head));     num = 0;
}
 
void add(int u,int v){     Edge[num].to = v;     Edge[num].next = head[u];     head[u] = num ++;
}
 
double dist(double x, double y, double xx, double yy){     return sqrt((x - xx) * (x - xx) + (y - yy) * (y - yy));
}
 
bool Search(){     queue<int> q;     dis = inf;     memset(dx,-1,sizeof(dx));     memset(dy,-1,sizeof(dy));     for(int i=0;i<n;i++){         if(lx[i] == -1){             q.push(i);             dx[i] = 0;         }     }     while(!q.empty()){         int u = q.front();         q.pop();         if(dx[u] > dis) break;         for(int i=head[u];i!=-1;i=Edge[i].next){             int v = Edge[i].to;             if(dy[v] == -1){                 dy[v] = dx[u] + 1;                 if(ly[v] == -1) dis = dy[v];                 else{                     dx[ly[v]] = dy[v] + 1;                     q.push(ly[v]);                 }             }         }     }     return dis != inf;
}
 
bool dfs(int u){     for(int i=head[u];i!=-1;i=Edge[i].next){         int v = Edge[i].to;         if(!vis[v] && dy[v] == dx[u] + 1){             vis[v] = true;             if(ly[v] != -1 && dy[v] == dis) continue;             if(ly[v] == -1 || dfs(ly[v])){                 ly[v] = u;                 lx[u] = v;                 return true;             }         }     }     return false;
}
 
int Hopcroft_Karp(){     int sum = 0;     while( Search() ){         memset(vis,false,sizeof(vis));         for(int i=0;i<n;i++){             if(lx[i] == -1 && dfs(i)) sum ++;         }     }     return sum;
}
 
int main()
{     int Case = 1;     scanf("%d",&T);     while(T--){         init();         scanf("%d%d",&t,&n);         for(int i=0;i<n;i++){             scanf("%lf%lf%lf",&a[i].x,&a[i].y,&a[i].v);         }         scanf("%d",&m);         for(int i=0;i<m;i++){             double xx, yy;             scanf("%lf%lf",&xx,&yy);             for(int j=0;j<n;j++){                 double zz = dist(xx, yy, a[j].x, a[j].y);                 if(a[j].v * t >= zz){                     add(j ,i);                 }             }         }         int ans = Hopcroft_Karp();         printf("Scenario #%d:\n%d\n\n",Case ++, ans);     }     return 0;
}

struct Link{     int cnt;     int k[maxn];
}link[maxn];
bool maps[maxn][maxn];
bool vis[maxn];
int limit;    // 上限
 
bool dfs(int u, int limit){     for(int i=1;i<=m;i++){         if(vis[i] == false && maps[u][i] == true){             vis[i] = true;             if(link[i].cnt < limit){                 link[i].k[ ++ link[i].cnt ] = u;                 return true;             }             for(int j=1;j<=link[i].cnt;j++){                 if(dfs(link[i].k[j], limit)){                     link[i].k[j] = u;                     return true;                 }             }         }     }     return false;
}
 
int solve(){
  int sum = 0;     memset(link,0,sizeof(link));     for(int i=1;i<=n;i++){         memset(vis,false,sizeof(vis));         if(dfs(i)) sum ++;     }     return sum;
}