Solution - 太虚梦华录 - 洛谷保存站

- 出题人题解。
- 听 Rubia 的时候想出来的一道题，本来是一道自以为有一点点难度的图论题，然后被 [yuruilin2026](https://www.luogu.com.cn/user/1294410) 一眼了。
- 还有，能请[某位出数据的同学](https://www.luogu.com.cn/user/1275540)解释一下你的测试点 #47 是怎么回事吗？谢谢~
---

观察题目可得两个权值相等对答案百害而无一利，所以只考虑大于与小于的情况。

首先考虑这样一个问题：

> 给定有向图 $G$，求最少需要添加多少条弧能使得 $G$ 强连通。

记入度为 $0$ 的强连通分量数量为 $a$，出度为 $0$ 的强连通分量数量为 $b$，答案即为 $\max(a, b)$。

然后将一个格点视为一个点，建图。注意到我们不能让一个链的长度大于 $2$，否则会浪费节点。

于是我们只能对图进行黑白染色。于是答案为 $\max(\lfloor\frac{n^k}{2}\rfloor, \lceil\frac{n^k}{2}\rceil) = \lceil\frac{n^k}{2}\rceil$。

```cpp
#include <bits/stdc++.h>
#define rint register int
#define rllong register long long
#define llong long long
using namespace std;

namespace FastIO {
    const int S=1<<23;
    char B[S],*H=B,*T=B,O[S],*Oa=O,*Ot=O+S-1;
    #define g (H==T&&(T=(H=B)+fread(B,1,S,stdin),H==T)?-1:*H++)
	#define putchar_(c) (*Oa++=(c),(Oa>Ot)?fwrite(O,1,S,stdout),Oa=O:0)
    template<typename I>
    inline void read(register I&x){
        register I s=0,w=1;register char c=g;
        for(;c<48||c>57;c=g)w=c==45?-1:1;
        for(;47<c&&c<58;c=g)s=s*10+c-48;x=s*w;
    }
    template<typename I>
    inline void write(register I x){
        if(!x){putchar_(48);return;}
        if(x<0){putchar_(45);x=-x;}
        register char*S=Oa,*T,tmp;
        while(x)*S++=x%10|48,x/=10;
        T=S;
        for(S--;Oa<=S;--S,++Oa)tmp=*Oa,*Oa=*S,*S=tmp;
        Oa=T;
    }
    inline void putchar(register char x){
    	putchar_(x);
	}
    struct F{~F(){fwrite(O,1,Oa-O,stdout);}}f;
}
#define read(n) FastIO::read(n)
#define write(n) FastIO::write(n)
#define putchar(n) FastIO::putchar(n)

llong n, k, tmp = 1;

int main(){
	read(k), read(n);
	for(rint i = 1; i <= k; ++i) tmp *= n;
    if(tmp <= 1){
        puts("0");
        return 0;
    }
	printf("%lld", tmp+1>>1);
	return 0;
}

```

正在渲染内容...