Warning: session_start(): open(/tmp/sess_a5de654ed13ad27748d4fff30a671f5c, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== ABC176 ====== ===== E ===== **题意：**给定一个矩阵，并且标了一些点，现在你可以选择矩阵上的任何一行和一列，摧毁这一行以及这一列上的所有目标点，问最多能摧毁多少个。（矩阵最大边长3e5，目标点不超过3e5个） **题解：**显然，最大值应该取在最多的那一行和最多的那一列，但是如果有相同的，我们要找的交叉点不是目标点的那个组合（显然如果是目标点，那么ans-1）。可以直接暴力取最多的行和最多的列。看似是$n^2$复杂度，但是由于目标点最多只有3e5个，所以最多找3e5个组合就能找到一个交叉点不是目标点的组合。


#include 
#include 
#include 
#include 
#include
#include 
using namespace std;
const int MAX = 3e5 + 20;
typedef long long ll;
struct ppp{
    int val, id;
    bool operator < (ppp a) const {
        return val > a.val;
    }
};
ppp hang[MAX], lie[MAX];
map  pic[MAX];
int main()
{
    int h, w, m;
    cin >> h >> w >> m;
    for (int i = 1; i <= m;i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        pic[x][y] = 1;
        hang[x].val++, lie[y].val++;
    }
    for (int i = 1; i <= max(h, w);i++)
        hang[i].id = i, lie[i].id = i;
    sort(hang + 1, hang + 1 + h);
    sort(lie + 1, lie + 1 + w);
    int ans = hang[1].val + lie[1].val - 1;
    {
        for (int i = 1; i <= h;i++)
        {
            if (i != 1 and hang[i].val != hang[i-1].val)
                break;
            for (int j = 1; j <= w;j++)
            {
                if (j!=1 and lie[j].val != lie[j-1].val)
                    break;
                if(pic[hang[i].id].count(lie[j].id) == 0)
                {
                    ans++;
                    cout << ans << endl;
                    return 0;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}