题解

ACGO欢乐赛#57 T5题解

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int maxm=1e6+5; 
int x[maxm],y[maxm];
const int maxn=1e3+5; 
struct node
{
	int id;
	int cnt;
};
node r[maxn],c[maxn];
bool cmp(node a,node b)
{
	return a.cnt<b.cnt;
}
int main()
{
    cin>>n>>m;
    if(m==0) 
    {
        cout<<0;
        return 0;
    }
    for(int i=1;i<=m;i++)
    {
        cin>>x[i]>>y[i];
        r[x[i]].cnt++;
        c[y[i]].cnt++;
        r[x[i]].id=x[i];
        c[y[i]].id=y[i];
    }
    sort(r+1,r+n+1,cmp);
    sort(c+1,c+n+1,cmp);
    bool flag[maxn][maxn];
    memset(flag,false,sizeof(flag));
    for(int i=1;i<=m;i++)
    {
    	flag[x[i]][y[i]]=true;
	}
	if(flag[r[n].id][c[n].id])
	{
		cout<<r[n].cnt+c[n].cnt-1;
	}
	else
	{
		cout<<r[n].cnt+c[n].cnt;
	}
    return 0;
}