• Time limit

  6000 ms

• Memory limit

  131072 kB

• OS

  Windows

• Source

吐槽

比赛时候一眼网络流，但数据范围显然不行，又看到这道题提交人数贼多，于是转向尝试各种贪心，什么两边都取最大值、一边取最大值另一边取最小值、两边都取最小值……很多贪心方法都自己出数据hack掉了，想不到怎么hack的思路再写网络流生成随机数据对拍，拍几百组没错再交，但还是WA个不停……比赛时这题最终通过率0.5%

赛后知道离散数学里有个东西叫做Hall定理，是匈牙利的理论基础，然而之前我们并不知道这么个东西……菜啊……等下学期离散学到这个再来填坑

能百度到的题解，看上去比较靠谱的都和hall定理沾边了，其他的贪心都没有证明，靠“显然”这类字眼蒙混过关，总感觉只是数据水放过去了，应该会被hack……

题解

官方题解——

可以算是官方题解的翻译

另外还有两个貌似（因为我还没看懂，留坑）靠hall定理保证正确性的“贪心”

源代码

#include
    
     #include
     
      const int MAXN=1e6+5;int T;int n;long long a[MAXN],b[MAXN];int main(){    scanf("%d",&T);    while(T--)    {        scanf("%d",&n);        a[0]=b[0]=0;        for(int i=1;i<=n;i++) scanf("%lld%lld",a+i,b+i),a[0]+=a[i],b[0]+=b[i];        long long ans=std::min(a[0],b[0]);        for(int i=1;i<=n;i++) ans=std::min(ans,a[0]+b[0]-a[i]-b[i]);        printf("%lld\n",ans);    }    return 0;}
     
    

留坑：总有一天我要整理一下这个博客混乱的标签