本文共 1279 字，大约阅读时间需要 4 分钟。
#include #include #include #include #include #include #include #include #include #include #include #include #include #define maxn 200010#define INF 0x7fffffff#define inf 10000000#define MOD 1000000007#define ull unsigned long long#define ll long longusing namespace std;vector g[1010];bool vis[1010][2];int d[1010][2], m, n;int dp(int i, int j, int fa){ if(vis[i][j]) return d[i][j]; vis[i][j] = true; int& ans = d[i][j]; ans = 2000; for(int k = 0; k < (int)g[i].size(); ++ k) if(g[i][k] != fa) ans += dp(g[i][k], 1, i); if(!j && fa >= 0) ++ ans; if(j || fa < 0) { int sum = 0; for(int k = 0; k < (int)g[i].size(); ++ k) if(g[i][k] != fa) sum += dp(g[i][k], 0, i); if(fa >= 0) ++ sum; ans = min(ans, sum); } return ans;}void init(){ for(int i = 0; i < n; ++ i) g[i].clear(); memset(vis, 0, sizeof(vis));}int main(){ int t; scanf("%d", &t); while(t --) { scanf("%d%d", &n, &m); init(); for(int i = 0; i < m; ++ i) { int a, b; scanf("%d%d", &a, &b); g[a].push_back(b); g[b].push_back(a); } int ans = 0; for(int i = 0; i < n; ++ i) if(!vis[i][0]) ans += dp(i, 0, -1); printf("%d %d %d\n", ans/2000, m-ans%2000, ans%2000); } return 0;}
转载于:https://www.cnblogs.com/avema/p/3774170.html