3-x-x

3-1-x

3-1-1

#include<bits/stdc++.h>
using namespace std;

const int N =505;

int match[N];

int g[N][N];

bool vis[N];

int n,k;

int ans;

bool Ntr(int u)
{
    for(int i=1;i<=n;i++)
    {
        if(g[u][i] && !vis[i])
        {
            vis[i]=1;
            if(!match[i] || Ntr(match[i]))
            {
                match[i]=u;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    cin>>n>>k;
    for(int i=1;i<=k;i++)
    {
        int u,v;
        cin>>u>>v;
        g[u][v]=1;
    }
    for(int i=1;i<=n;i++)
    {
        memset(vis,0,sizeof(vis));
        if(Ntr(i)) ans++;
    }
    cout<<ans;
    return 0;
}

3-1-2

#include<bits/stdc++.h>
using namespace std;

const int N = 205;
const int M = 205*205;

int n;
int idx;
int g[N][N];
int ans;

vector<int> lft;

vector<int> e[M];
bool vis[M];
int match[M];

inline void Link(int u,int v)
{
    if(u && v)
    {
        e[u].push_back(v);
        // cout<<u<<" "<<v<<endl;
    }
}

bool Ntr(int u)
{
    for(int v : e[u])
    {
        if(!vis[v])
        {
            vis[v]=1;
            if(!match[v] || Ntr(match[v]))
            {
                match[v]=u;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    cin>>n;
    char c=getchar();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            char ch=getchar();
            if(ch=='0')
            {
                g[i][j]=++idx;
                if((i^j)&1) lft.push_back(idx);
            }
        }
        c=getchar();
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(g[i][j])
            {
                if(i-2>=1)
                {
                    if(j-1>=1) Link(g[i][j],g[i-2][j-1]);
                    if(j+1<=n) Link(g[i][j],g[i-2][j+1]);
                }
                if(i-1>=1)
                {
                    if(j-2>=1) Link(g[i][j],g[i-1][j-2]);
                    if(j+2<=n) Link(g[i][j],g[i-1][j+2]);
                }
                if(i+2<=n)
                {
                    if(j-1>=1) Link(g[i][j],g[i+2][j-1]);
                    if(j+1<=n) Link(g[i][j],g[i+2][j+1]);
                }
                if(i+1<=n)
                {
                    if(j-2>=1) Link(g[i][j],g[i+1][j-2]);
                    if(j+2<=n) Link(g[i][j],g[i+1][j+2]);
                }
            }
        }
    }
    for(int u : lft)
    {
        for(int i=1;i<=idx;i++) vis[i]=0;
        if (Ntr(u)) ans++;
    }
    cout<<idx-ans;
    return 0;
}

3-1-3

#include<bits/stdc++.h>
using namespace std;

inline void Read(int &ans)
{
    ans=0;
    bool flag=0;
    char ch=getchar();
    while(~ch && !isdigit(ch))
    {
        flag|=(ch=='-');
        ch=getchar();
    }
    while(~ch && isdigit(ch))
    {
        ans=ans*10+(ch^48);
        ch=getchar();
    }
    if(flag) ans=-ans;
}

char c[100];
inline void Write(int ans)
{
    if(ans<0)
    {
        putchar('-');
        ans=-ans;
    }
    int cnt=0;
    while(ans)
    {
        c[++cnt]=(ans%10);
        ans/=10;
    }
    while(cnt)
    {
        putchar(c[cnt]^48);
        cnt--;
    }
}

inline int Dis(int x,int y,int xx,int yy) {return abs(x-xx)+abs(y-yy);}

struct people {int x,y,xx,yy,t;}node[505];

int n,ans;
bool vis[505];
int match[505];

vector<int> e[505];

inline bool Link(people a,people b)
{
    int t=a.t+Dis(a.x,a.y,a.xx,a.yy)+Dis(a.xx,a.yy,b.x,b.y);
    if(t<b.t) return true;
    else return false;
}

bool Ntr(int u)
{
    for(int v : e[u])
    {
        if(!vis[v])
        {
            vis[v]=1;
            if(!match[v] || Ntr(match[v]))
            {
                match[v]=u;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    // freopen("working.out","w",stdout);
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++) e[i].clear();
        memset(match,0,sizeof(match));
        for(int i=1;i<=n;i++) 
        {
            int t=0;
            Read(t);
            t*=60;
            int x;
            Read(x);
            t+=x;
            Read(node[i].x);
            Read(node[i].y);
            Read(node[i].xx);
            Read(node[i].yy);
            node[i].t=t;
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                if(Link(node[i],node[j])) {e[i].push_back(j);}
            }
        }
        ans=n;
        for(int i=1;i<=n;i++) 
        {
            memset(vis,0,sizeof(vis));
            if(Ntr(i)) ans--;
        }
        cout<<ans<<endl;
    }
    return 0;
}