模拟，利用图的性质，将当前度数最大的点（假设度数为d(x)）删除的同时，把紧接着的前d(x)大的度数分别减一。如果最终可以全部相消，那么就是一个简单图，否则不是。
View Code 1 #include2 #include 3 #include 4 #include 5 #include 6 7 #define REP(i, n) for (int i = 0; i < (n); i++) 8 using namespace std; 9 10 multiset cnt;11 stack tmp;12 13 int main() {14 int T, n, x;15 cin >> T;16 while (T-- && cin >> n) {17 int sum = 0;18 cnt.clear();19 REP(i, n) {20 cin >> x;21 if (x) cnt.insert(x);22 sum += x;23 }24 if ((sum & 1) || *cnt.rbegin() >= n) {25 puts("no");26 } else {27 while (true) {28 if (cnt.size() == 0) {29 puts("yes");30 break;31 }32 if (cnt.size() == 1) {33 puts("no");34 break;35 }36 int mx = *cnt.rbegin();37 cnt.erase(cnt.find(mx));38 if (mx > cnt.size()) {39 puts("no");40 break;41 }42 int t;43 while (!tmp.empty()) tmp.pop();44 REP(i, mx) {45 t = *cnt.rbegin();46 if (t > 1) tmp.push(t - 1);47 cnt.erase(cnt.find(t));48 }49 while (!tmp.empty()) {50 cnt.insert(tmp.top());51 tmp.pop();52 }53 }54 }55 }56 return 0;57 }
——written by Lyon