AcWing P373 車的放置

Analysis

这道题是二分图匹配，设可以放車的的地方的坐标为（i，j），则连一条i到j的有向边（注意是有向边），然后再跑匈牙利算法就好了。时间复杂度是O(nm(n+m))，在1≤n,m≤200的情况下可以接受。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define maxn 205

 using namespace std;

 inline int read()

 {

     int x=;

     bool f=;

     char c=getchar();

     for(; !isdigit(c); c=getchar()) if(c=='-') f=;

     for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';

     if(f) return x;

     return -x;

 }

 inline void write(int x)

 {

     if(x<){putchar('-');x=-x;}

     if(x>)write(x/);

     putchar(x%+'');

 }

 struct node

 {

     int to,nex;

 }edge[*(maxn*maxn+)];

 int n,m,t,cnt,ans;

 int head[*(maxn*maxn+)],match[*(maxn*maxn+)];

 bool map[maxn][maxn],book[*(maxn*maxn+)];

 inline void add(int x,int y)

 {

     cnt++;

     edge[cnt].to=y;

     edge[cnt].nex=head[x];

     head[x]=cnt;

 }

 inline bool dfs(int u)

 {

     for(int i=head[u];i;i=edge[i].nex)

     {

         int v=edge[i].to;

         if(!book[v])

         {

             book[v]=;

             if(!match[v]||dfs(match[v]))

             {

                 match[v]=u;

                 return true;

             }

         }

     }

     return false;

 }

 int main()

 {

     n=read();m=read();t=read();

     for(int i=;i<=t;i++)

     {

         int x,y;

         x=read();y=read();

         map[x][y]=true;

     }

     for(int i=;i<=n;i++)

         for(int j=;j<=m;j++)

             if(!map[i][j])

             {

                 add(i,j);

             }

     for(int i=;i<=n;i++)

     {

         memset(book,,sizeof(book));

         if(dfs(i))ans++;

     }

     write(ans);

     return ;

 }

请各位大佬斧正