因为只会打暴力，而且发现旁边的人切题了(然而这个人做法假了)

于是这场心态崩了，导致不能很专注的思考性质和检查代码

所以还是没能做到不被别人影响

T1 一般图带权多重匹配

垃圾费用流题，然而我没想到

考虑如何将匹配的过程转化，发现匹配的过程是两个点同时减 \(1\)

于是就可以将每个点拆成两个点，并分别与s和t连\(\frac{a_i}{2}\)的流量

分别考虑奇数和偶数，偶数按照上述连边即可

奇数最后一定是两两匹配，于是状压枚举一半的奇数，分别与 \(s\)和 \(t\)补上少的 \(1\)

T3 传染

\(O(n^2)\) 暴力，从 x 点一直传染直到不能传染，就从 x 向最终能传染到的点连边

然后强联通缩点，dag 上没有入度的点的个数即为答案

考虑一种方法优化 dfs ，即能将传染的过程在节点上打标记，一个点只会被传染一次

考虑点分树，由于点分树上两点的 lca 是两点在原树路径上一点，于是可以枚举 x 的祖先 f 并按距离升序枚举 f 的子树内的点，此时有了单调性于是可以标记，从所有点开始传染一边的复杂度变成了 \(O(n\log n)\)

接着思考从 x 传染的过程，本质上是从 x 沿着 dag 走到没有出度的点

于是有了这样一种方法，可以遍历点并开始传染，然后将所有能传染到的点(包括自身)逆序加入到一个 vector，在遍历完后将 vector 翻转

不难发现，这样的操作后若将 vector 内的元素替换成所属的 dag 的节点，那 vector 中的顺序满足 x 一定在 x 能到的点之后出现，此时可以再传染一边，扫到的没有被标记的点的个数为答案

代码

T1

#include<cmath>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#define il inline
const int N=6e3+11;
const int inf=0x3f3f3f3f;
using namespace std;
struct qxxx{
	int v,next,w,cost;
}cc[2*N];
bool vis[N];
int n,s,t;
int a[N];
int d[N],path[N];
int first[N],cnt;
int c[N][N];
queue<int>dui;
vector<int>odd;
il int min_(int x,int y){return x>y?y:x;}
il int read(){
	int s=0;char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return s;
}
il int js(int x){
	int ans=0;
	for(;x;x-=(x&-x),++ans);
	return ans;
}
il void qxx(int u,int v,int w,int c){
	cc[++cnt]={v,first[u],w,c};
	first[u]=cnt;
}
il void add(int u,int v,int w,int c){
	qxx(u,v,w,c);
	qxx(v,u,0,-c);
}
il void init(){
	cnt=1;
	memset(cc,0,sizeof(cc));
	memset(first,0,sizeof(first));
}
bool spfa(){
	memset(d,0x3f,sizeof(d));
	memset(vis,0,sizeof(vis));
	memset(path,0,sizeof(path));
	int x;d[s]=0,vis[s]=1;dui.push(s);
	while(dui.size()){
		x=dui.front();
		dui.pop();vis[x]=0;
		for(int v,i=first[x];i;i=cc[i].next){
			if(!cc[i].w)continue;
			v=cc[i].v;
			if(d[v]>cc[i].cost+d[x]){
				path[v]=i;
				d[v]=cc[i].cost+d[x];
				if(!vis[v]){vis[v]=1,dui.push(v);}
			}
		}
	}return d[t]!=inf;
}
int cost_flow(){
	int mn=inf,cost=0;
	while(spfa()){
		mn=inf;
		for(int i=path[t];i;i=path[cc[i^1].v]){
			mn=min_(mn,cc[i].w);
		}
		for(int i=path[t];i;i=path[cc[i^1].v]){
			cc[i].w-=mn;
			cc[i^1].w+=mn;
			cost+=mn*cc[i].cost;
		}
	}return cost;
}
int main(){
	freopen("match.in","r",stdin),freopen("match.out","w",stdout);
	n=read();
	for(int i=1;i<=n;++i){
		a[i]=read();
		if(a[i]&1)odd.push_back(i);
	}
	for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)c[i][j]=read();
	if(odd.size()&1){cout<<-1<<endl;return 0;}
	s=2*n+1,t=2*n+2;
	int ans=inf;
	for(int i=0;i<(1<<odd.size());++i){
		if(js(i)!=(odd.size()>>1))continue;
		init();
		for(int j=1;j<=n;++j){
			if(a[j]&1)continue;
			add(s,j,a[j]>>1,0);
			add(j+n,t,a[j]>>1,0);
		}
		for(int x,j=0;j<odd.size();++j){
			x=odd[j];
			if((1<<j)&i){
				add(s,x,1+(a[x]>>1),0);
				add(x+n,t,a[x]>>1,0);
			}
			else{
				add(s,x,a[x]>>1,0);
				add(x+n,t,1+(a[x]>>1),0);
			}
		}
		for(int j=1;j<=n;++j)
			for(int k=1;k<=n;++k){
				add(j,k+n,inf,c[j][k]);
			}
		ans=min_(ans,cost_flow());
	}cout<<ans<<endl;
}

T3

#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define il inline
const int inf=1e9;
const int N=3e5+11;
struct vct_{
	int v,d;vct_(){}
	vct_(int v_,int d_){v=v_,d=d_;}
	friend bool operator<(vct_ a,vct_ b){
		return a.d<b.d;
	}
};
bool vis[N];
int n;
int mx_siz,rt;
int p[N];
int siz[N],r[N];
vector<int>tp,tmp;
vector<vct_>vct[N];
vector<vct_>cs[N],vs[N];
il int max_(int x,int y){return x>y?x:y;}
il int min_(int x,int y){return x>y?y:x;}
il int read(){
	int s=0;char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9')s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
	return s;
}
void get_siz(int x,int fa){
	siz[x]=1;int v;
	for(vct_ y : vct[x]){
		v=y.v;if(v==fa||vis[v])continue;
		get_siz(v,x);
		siz[x]+=siz[v];
	}
}
void get_rt(int x,int fa,int now){
	int v,mx=0;
	for(vct_ y : vct[x]){
		v=y.v;if(v==fa||vis[v])continue;
		get_rt(v,x,now);
		mx=max_(mx,siz[v]);
	}mx=max_(mx,now-siz[x]);
	if(mx_siz>mx)mx_siz=mx,rt=x;
}
void dfs(int x,int fa,int dep,int root){
	if(dep>inf)return;int v;
	vs[root].push_back({x,dep});
	cs[x].push_back({root,dep});
	for(vct_ y : vct[x]){
		v=y.v;if(v==fa||vis[v])continue;
		dfs(v,x,dep+y.d,root);
	}
}
void div(int x){
	vis[x]=1;
	dfs(x,0,0,x);
	sort(vs[x].begin(),vs[x].end());
	int v;for(vct_ y : vct[x]){
		v=y.v;if(vis[v])continue;
		mx_siz=inf;get_siz(v,0);
		get_rt(v,0,siz[v]);div(rt);
	}
}
void maketp(int x){
	vis[x]=1;
	for(vct_ e : cs[x]){
		while(p[e.v]<(int)vs[e.v].size()){
			vct_ f=vs[e.v][p[e.v]++];
			if(vis[f.v])continue;
			if(f.d+e.d>r[x]){--p[e.v];break;}
			maketp(f.v);
		}
	}tp.push_back(x);
}
int main(){
	freopen("infect.in","r",stdin),freopen("infect.out","w",stdout);
	n=read();for(int i=1;i<=n;++i)r[i]=read();
	for(int x,y,z,i=1;i<n;++i){
		x=read(),y=read(),z=read();
		vct[x].push_back(vct_(y,z));
		vct[y].push_back(vct_(x,z));
	}
	mx_siz=inf,get_siz(1,0),get_rt(1,0,n);div(rt);
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;++i){
		if(vis[i])continue;
		maketp(i);
	}
	tmp=tp;tp.clear();
	reverse(tmp.begin(),tmp.end());
	memset(p,0,sizeof(p));
	memset(vis,0,sizeof(vis));
	int ans=0;
	for(int v : tmp){
		if(vis[v])continue;
		maketp(v);++ans;
	}cout<<ans<<endl;
}