题意:给定一个图,节点可以放灯,要求用最少的灯覆盖所有的边(每盏灯能覆盖该节点邻接的边),满足条件的同时求该前提下尽量多的被两盏灯照亮的边数
条件二转化为求尽量少的被一盏灯照亮的边数,两个条件都是求min,我们需要构造一个条件一取决定性作用的式子,
令\(f(a,b)=Ma+b\),其中\(a\)为条件一的最优解,\(M\)为一个足够大的数,以至于\(b\)的最大值都小于\(M\)(更精确的应该是\(M>b_{max}-a_{min}\)),那么\(b\)为满足\(a\)前提下的最优解,所以我们就是在图上DP求解这条式子的min,两个系数分别对应不同的解
有一些实现上的细节需要注意,dp方程应该设\(dp[i][j]\):父节点灯\([j==1]\)与否的情况下\(i\)子树及沿向父亲的边的最优解
为什么点灯要从父亲那里设?因为如果设为子树根的情况的话,遍历森林求解ans时会十分繁琐
而父亲节点只要设置一个0的不存在的根,一切都会十分好办
不过这还是取决于编写习惯
还有一个要小心的地方是若父亲情况为0时,子树的根节点也是可以为0的,因为父节点可以是不存在的根
ChromeOS用某IDE无法注释中文,凑合看
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#define rep(i,j,k) for(register int i=j;i<=k;i++)
#define rrep(i,j,k) for(register int i=j;i>=k;i--)
#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])
#define iin(a) scanf("%d",&a)
#define lin(a) scanf("%lld",&a)
#define din(a) scanf("%lf",&a)
#define s0(a) scanf("%s",a)
#define s1(a) scanf("%s",a+1)
#define print(a) printf("%lld",(ll)a)
#define enter putchar('\n')
#define blank putchar(' ')
#define println(a) printf("%lld\n",(ll)a)
#define IOS ios::sync_with_stdio(0)
using namespace std;
const int maxn = 1e4+11;
const double eps = 1e-10;
typedef long long ll;
const int oo = 0x3f3f3f3f;
ll read(){
ll x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll dp[maxn][2];
int to[maxn<<1],nxt[maxn<<1],head[maxn],tot;
void init(){
memset(head,-1,sizeof head);
tot=0;
}
void add(int u,int v){
to[tot]=v;nxt[tot]=head[u];head[u]=tot++;
swap(u,v);
to[tot]=v;nxt[tot]=head[u];head[u]=tot++;
}
ll M;
// bool isleaf(int u,int fa){
// int cnt=0;
// erep(i,u){
// int v=to[i];
// if(v==fa)continue;
// cnt++;
// if(cnt==1)return 0;
// }
// return 1;
// }
// int deg[maxn];
// ll DP(int u,int fa,int flag){
// if(~dp[u][flag]) return dp[u][flag];
// if(isleaf(u,fa)) return dp[u][flag]=flag*M;
// ll ans=flag*M;
// if(flag==1) erep(i,u){
// int v=to[i];
// if(v==fa)continue;
// ans+=min(DP(v,u,0)+1,DP(v,u,1));
// }else erep(i,u){
// int v=to[i];
// if(v==fa)continue;
// ans+=DP(v,u,1)+1;
// }
// return dp[u][flag]=ans;
// }
bool vis[maxn][2];
ll DP(int u,int fa,int flag){//fujiedianfangdengwei true
if(vis[u][flag])return dp[u][flag];
vis[u][flag]=1;
//ru guo u shi gen na ye ke yi bu fang deng jiagen wei 0 gen yewei 0
if(flag==0){
dp[u][0]=M+bool(fa!=0);//virtual root
erep(i,u){
int v=to[i];
if(v==fa)continue;
dp[u][0]+=DP(v,u,1);
}
ll tmp=1ll<<60;
if(fa==0){
tmp=0;
erep(i,u){
int v=to[i];
if(v==fa)continue;
tmp+=DP(v,u,0);
}
}
return dp[u][0]=min(dp[u][0],tmp);//ok
}else{
// dp[u][1]+=min(DP(v,u,1),DP(v,u,0));//cannot dfs
ll tmp1=M;//u fangdeng
erep(i,u){
int v=to[i];
if(v==fa)continue;
tmp1+=DP(v,u,1);
}
ll tmp2=1;//bufangdeng
erep(i,u){
int v=to[i];
if(v==fa)continue;
tmp2+=DP(v,u,0);
}
return dp[u][1]=min(tmp1,tmp2);
}
}
int main(){
int T=read();
while(T--){
init();
memset(dp,-1,sizeof dp);
memset(vis,0,sizeof vis);
int n=read();
int m=read();
rep(i,1,m){
int u=read();u++;
int v=read();v++;
add(u,v);
}
M=2333;
ll ans=0;
rep(i,1,n){
if(!vis[i][0]){
ans+=DP(i,0,0);
}
}
printf("%lld %lld %lld\n",ans/M,m-(ans%M),ans%M);
}
return 0;
}