给你一个图 在尽量少的节点上放灯 使得所有边所有边都被照亮 每盏灯照亮以他为端点的所有边
求在灯总数最小的前提下 被两盏灯照亮的边数尽量大（即被一条边照亮的边数尽量小）
另x = Ma + c (a是灯的数量，c是被两盏灯照亮边数）转换求x 最小
M是一个很大的数 x取最小时 x/m整数部分就是所求灯最小值 x%m就是被一条边照亮的边数
M比 c的最大理论值和a的最小理论值差 还要大的数 那么x都是a起到决定性作用 a相同时在取决于c
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 1010;
vector <int> adj[maxn];
int vis[maxn][2], dp[maxn][2], n, m;
int dfs(int i, int j, int f)
{
if(vis[i][j])
return dp[i][j];
vis[i][j] = 1;
int& ans = dp[i][j];
ans = 2000;
for(int k = 0; k < adj[i].size(); k++)
if(adj[i][k] != f)
ans += dfs(adj[i][k], 1, i);
if(!j && f >= 0)//不是根并且父节点没有放灯 那么被一盏灯照亮的边加1
ans++;
if(j || f < 0)//是根 或者 父节点已经放了灯才能不放
{
int sum = 0;
for(int k = 0; k < adj[i].size(); k++)
if(adj[i][k] != f)
sum += dfs(adj[i][k], 0 , i);
if(f >= 0)//不放的话父节点肯定已经放了 那么被一盏灯照亮的边加1
sum++;
ans = min(ans, sum);
}
return ans;
}
int main()
{
int T, u, v;
scanf("%d", &T);
while(T--)
{
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
adj[i].clear();
for(int i = 0; i < m; i++)
{
scanf("%d %d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
memset(vis, 0 ,sizeof(vis));
int ans = 0;
for(int i = 0; i < n; i++)
if(!vis[i][0])
ans += dfs(i, 0, -1);
printf("%d %d %d\n", ans/2000, m-ans%2000, ans%2000);
}
return 0;
}