BUET Inter-University Programming Contest - 2011 E, UVa-12428 : Enemy at the Gates
問題概要
ノード数N(<10^5)、辺数M(
解法
まず星グラフを考える。その後辺数が余っていたら頂点を一つ選んで既にあるクリークにその頂点を含むクリークになるように辺を追加する。First Acceptだったっぽい。
acceptされたコード
計算量O(sqrt(M))。
#include <cstdio> using namespace std; typedef long long int64; int64 N, M; void init(){ scanf("%lld%lld", &N, &M); } int solve(){ if(M < N){ return M; } int ans = N-2; M -= N - 1; for(int cur=1;M>0;cur++){ ans--; M -= cur; } return ans; } int main(){ int T; scanf("%d", &T); for(;T--;){ init(); printf("%d\n", solve()); } return 0; }