题答题好玩。

原题链接，本题题意细节极多，强烈建议读题后阅读。

题意：给一些图论算法构造数据，每次放过一个卡掉一个，定义“卡掉”的标准是代码中的计数器自加超过 $10^6$ 次。只有你构造的数据中整数的个数小于一个给定值 $T$ 时才能获得满分。

---

$\mathrm{subtask\ 1(3pts)}$

放过 $Dijkstra$ 卡掉 $Floyd$，$T=107$。

送温暖的。

观察两个代码，都是正常的写法。但我们注意到 $Floyd$ 中计数器放在三层循环中，也就是其值就是点数的立方，那么 $Floyd$ 最多只能跑 $\sqrt[3]{10^6}=100$ 的点，于是我们只要造一个 $101$ 个点的图就好了，为了满足 $T=107$ 的限制，图里一条边也没有。

#include<iostream>
#include<cstdio>
using namespace std;
int n,q;
int main()
{
    freopen("1.txt","w",stdout);
    n=101;
    cout<<n<<endl;
    for(int i=0;i<n;++i)
        cout<<0<<endl;
    q=1;
    cout<<q<<endl;
    cout<<"0 0"<<endl;
    return 0;
}

数据中一共有 $105$ 个整数。

---

$\mathrm{subtask\ 2(7pts)}$

放过 $Floyd$ 卡掉 $Bellman-Ford$，$T=2222$。

根据 $sub1$ 得出的结论，我们的点数不能多于 $100$。观察 $Bellman-Ford$ 的实现，发现计数器每跑一轮就会增加 $\sum n_i$，由于代码在一轮下来没有松弛成功的情况下就会推出，所以我们要让它跑满 $V-1$ 轮。

考虑 $Bellman-Ford$ 其实是一个顺推的过程，比如如果图是一条 $0\rightarrow V-1$ 的有向链，其实一轮就已经完成了松弛。

那么我们反过来，把图建成一条 $V-1\rightarrow0$ 的有向链，这样每次松弛会恰好成功一次，每次询问的时候起点设成 $V-1$ 就可以卡满。

询问尽量多，$Q=10$，这样会进行 $Q(V-1)\sum n_i=98010$ 次运算，远远不到 $10^6$。

其实这样构造数据中的整数只有 $320$ 个，浪费了很多资源。注意到其实题目没有要求是简单图，我们大可以把多出来的整数变成重边塞进去。

算一下 $\frac{2222-22-100}{100\times 2}=10.5$，每条边都可以变成十条重边。这样 $Q(V-1)\sum n_i=980100$，还差一点。

其实还是有点浪费，我们考虑利用刚才扔掉的 $0.5$ 条边。其实我们只要每两个点连出去 $21$ 条边就是合法的，那么我们直接分奇偶连 $10$ 和 $11$ 条重边，这样 $Q(V-1)\sum n_i=1039500$，刚刚好。

#include<iostream>
#include<cstdio>
using namespace std;
int n,q;
int main()
{
    freopen("2.txt","w",stdout);
    n=100;
    cout<<n<<endl<<11<<endl;
    for(int i=1;i<=11;++i)
        cout<<n-1<<" 1 ";
    cout<<endl;
    for(int i=1;i<n;++i)
    {
        if(i&1)
        {
            cout<<"10 ";
            for(int j=1;j<=10;++j)
                cout<<i-1<<" 1 ";
        }
        else
        {
            cout<<"11 ";
            for(int j=1;j<=11;++j)
                cout<<i-1<<" 1 ";
        }
        cout<<endl;
    }
    q=10;
    cout<<q<<endl;
    while(q--)
        cout<<n-1<<" 0"<<endl;
    return 0;
}

数据中一共有 $2222$ 个整数。

---

$\mathrm{subtask\ 3(8pts)}$

放过 $Bellman-Ford$ 卡掉 $Floyd$，$T=105$。

你怎么又在送啊。

和 $sub1$ 一模一样即可。

#include<iostream>
#include<cstdio>
using namespace std;
int n,q;
int main()
{
    freopen("3.txt","w",stdout);
    n=101;
    cout<<n<<endl;
    for(int i=0;i<n;++i)
        cout<<0<<endl;
    q=1;
    cout<<q<<endl<<"0 0"<<endl;
    return 0;
}

数据中一共有 $105$ 个整数。

---

$\mathrm{subtask\ 4(17pts)}$

放过 $Floyd$ 卡掉 $Dijkstra$，$T=157$。

这个有点难度。

随了很多组数据，发现这个 $Dijkstra$ 表现出色且稳定，数据规模还限制得这么小，真的能卡掉吗？

发现题目中限制的是边权的绝对值，也就是说可以有负权边，众所周知 $Dijkstra$ 在有负权边的时候是可以卡成指数级别的，我们可以在这个上面做文章。

构造这种数据的核心在于造一个长链出来，先用小的正边权把 $Dijkstra$ 骗到链尾，然后外挂很多点，点的入边是一个大的正权边，出边是一个绝对值比入边大的负权边，这样最短路实际上是走外挂点的那条，但是 $Dijkstra$ 已经被链骗过去更新了一遍整个图了，所以它会重新松弛，多重复几次就变成指数级了，这样算一下其实 $T=157$ 还很松，这里构造的数据 $V=33,Q=10$。

#include<iostream>
#include<cstdio>
using namespace std;
int n,q;
int main()
{
    freopen("4.txt","w",stdout);
    n=33;
    cout<<n<<endl;
    for(int i=2;i<n;i+=2)
    {
        cout<<"2 "<<i-1<<" "<<(1<<(17-i/2-1))<<" "<<i<<" 0"<<endl;
        cout<<"1 "<<i<<" "<<-(1<<(17-i/2))<<" "<<endl;
    }
    cout<<0<<endl;
    q=10;
    cout<<q<<endl;
    while(q--)
        cout<<0<<" "<<n-1<<endl;
    return 0;
}

数据中一共有 $151$ 个整数。

---

$\mathrm{subtask\ 5(10pts)}$

放过 $Dijkstra$ 卡掉 $Bellman-Ford$，$T=1016$。

用 $sub2$ 的方法构造即可。$T$ 限制变紧的同时我们没有了 $V\leq 100$ 的限制，于是直接把点数开到最大，剩余的整数尽量造重边即可。

#include<iostream>
#include<cstdio>
using namespace std;
int n,q;
int main()
{
    freopen("5.txt","w",stdout);
    n=300;
    cout<<n<<endl<<0<<endl;
    for(int i=1;i<n;++i)
        if(i<=47)
            cout<<"2 "<<i-1<<" 1 "<<i-1<<" 1"<<endl;
        else
            cout<<"1 "<<i-1<<" 1"<<endl;
    q=10;
    cout<<q<<endl;
    while(q--)
        cout<<n-1<<" 0"<<endl;
    return 0;
}

数据中一共有 $1014$ 个整数（似乎还能再加一条重边，不过已经足够卡掉了）。

---

$\mathrm{subtask\ 6(19pts)}$

放过 $Bellman-Ford$ 卡掉 $Dijkstra$，$T=143$。

还是考虑刚才的做法，但是我们用掉的整数刚好比 $143$ 多了一点。

运行一下 $Dijkstra$ 跑一下刚才造的那组数据，发现其实在跑到第 $6$ 组询问的时候已经 $TLE$ 了，也就是说我们多了四组没用的询问。

删了他们，少了 $8$ 个整数，$151$ 刚好变成 $143$。

#include<iostream>
#include<cstdio>
using namespace std;
int n,q;
int main()
{
    freopen("6.txt","w",stdout);
    n=33;
    cout<<n<<endl;
    for(int i=2;i<n;i+=2)
    {
        cout<<"2 "<<i-1<<" "<<(1<<(18-i/2-1))<<" "<<i<<" 0"<<endl;
        cout<<"1 "<<i<<" "<<-(1<<(18-i/2))<<" "<<endl;
    }
    cout<<0<<endl;
    q=6;
    cout<<q<<endl;
    while(q--)
        cout<<0<<" "<<n-1<<endl;
    return 0;
}

数据中一共有 $143$ 个整数。

---

$\mathrm{subtask\ 7(11pts)}$

图染色，要求相邻点颜色不同，最小化颜色数，让你放过的算法是钦定能过的，卡掉暴力，$T=3004$。

别送了，别送了。

暴力的实现是从小到大暴力 check 答案，那我们让答案很大就好了。

完全图！我们来算一下，这个完全图最大可以有 $55$ 个点，然后我们只要连边即可，得到 $E=1485$……

慢着？题目里面说 $V>70,E>1500$？

那我们只能多来几个点补到 $71$，然后在他们之间连边把边数凑到 $1501$。

刚才完全图加上 $V$ 和 $E$ 一共用掉了 $2\times 1485+2=2972$ 个点，还剩 $32$ 个点，可以连 $16$ 条边。而我们刚好需要 $16$ 条边达到 $1501$，问题解决。

#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int main()
{
    freopen("7.txt","w",stdout);
    n=71,m=1501;
    cout<<n<<" "<<m<<endl;
    for(int i=1;i<55;++i)
        for(int j=i+1;j<=55;++j)
            cout<<i-1<<" "<<j-1<<endl;
    for(int i=55;i<n;++i)
        cout<<0<<" "<<i<<endl;
    return 0;
}

数据中一共有 $3004$ 个整数。

---

$\mathrm{subtask\ 8(25pts)}$

染色，放过暴力，让你卡掉的算法是钦定过不了的。

道理我都懂，这一下子送 $25$ 分是？

怎么放过这个暴力？把颜色数造得非常小即可。那我们点数开到最大 $V=999$，然后先来连成一个环，然后其实就是人类智慧，只要把边凑够，没有度数特别大的点就好了。我的做法是再来一轮，每次 $i-1$ 和 $2i-1$ 连边，这样最后还需要连 $5$ 条才能到 $1501$ 直接首尾相连即可。这样算一下一共 $2\times 1501+2=3004$，刚刚好。

#include<iostream>
#include<cstdio>
using namespace std;
int n,m;
int main()
{
    freopen("8.txt","w",stdout);
    n=999,m=1501;
    cout<<n<<" "<<m<<endl;
    for(int i=1;i<n;++i)
        cout<<i-1<<" "<<i<<endl;
    for(int i=2;i<<1<=n;++i)
        cout<<i-1<<" "<<(i<<1)-1<<endl;
    for(int i=0;i<5;++i)
        cout<<i<<" "<<n-1-i<<endl;
    return 0;
}

数据中一共有 $3004$ 个整数。

---

至此整个题目完结，这确实是一个非常有趣的题目，不同任务难易有梯度，唯一感觉不太好的地方是让我很期待的后两个 $subtask$ 甚至比前面还要简单，大大低于我的预期。