题解

思路概述

• 小修和小栋要求一致地选择一批边，使得在各自的图中形成“森林 / 环套树森林”。这恰好是两个拟图拟阵（graphic / bicircular matroid）的交问题：在一方的图中允许的独立集是森林（若 type = 1），或是每个连通块至多含一条环的伪森林（若 type = 2）；另一方同理。我们需要在交集中找到权值最大的独立集，即带权拟阵交。
• 由于 $m \le 300$，可以直接套用经典的带权拟阵交增广算法。算法从一个空集合开始，反复在“交换图”中寻找正收益的增广路：
  • 当前选择集合记为 $S$。构造一张有向图，顶点是所有边。若把集合中的边 i 去掉后能让未选的某条边 j 在某个拟阵中保持独立，则连一条 i → j 的有向边；若把 j 加入后仍独立，则连 j → i。
  • 把所有可以直接加入集合且保持两个拟阵独立的边作为源点，所有可以直接从集合中删去的边作为汇点，边权为交换后权值的变化。若存在从源到汇的正权路径，就按照路径翻转选中状态，更新答案；否则算法结束。
• 图是拟阵的标准交换图构造，保证每次找到的路径都能维持两个拟阵的独立性。重复上述过程直到无法增广即得到最优解。

实现细节

• 两个拟阵都可以用并查集维护：对森林约束，只要加入的边不形成环即可；对环套树森林，每个连通块允许有一个“额外”度数，用并查集维护时只需记录每个块还剩多少冗余即可。代码里 DSU 结构的 merge / mergeck 就是在线检查“若把某条边加入（或移除）是否会违反度数限制”。
• 每轮先把当前已经选中的边删去再重建两侧森林，之后枚举每条已选边作为交换图中的顶点，用上述并查集判断与所有未选边之间的可互换关系，建图。
• 交换图通过 SPFA 寻找最长路（因为我们希望权值增加），路径上记录前驱，找到收益为正的终点后沿着前驱翻转选中状态并更新总权值。若最大收益 $≤0$，说明已经无法改进，算法终止。

复杂度

每次增广需要 $O(m^2)$ 规模的建图与最短路，且增广次数最多 $O(m)$，总体复杂度 $O(m^3)$，在本题数据范围内可行；空间复杂度 $O(m)$。

#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<bitset>
#include<cstdio>
#include<random>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
#define her1 20081214
#define cht 998244353
#define IV void
#define ull unsigned long long
#define mem(x,val) memset(x,val,sizeof x)
#define F(i,j,n)for(register int i=j;i<=n;i++)
#define D(i,j,n)for(register int i=j;i>=n;i--)
#define E(i,now)for(register int i=first[now];i;i=e[i].nxt)
#define FL(i,j,n)for(register i64 i=j;i<=n;i++)
#define DL(i,j,n)for(register i64 i=j;i>=n;i--)
#define EL(i,now)for(register i64 i=first[now];i;i=e[i].nxt)
ll read(){
	ll ans=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9')ans=ans*10+c-'0',c=getchar();
	return ans*f;
}
using i64 = int;
#include "assert.h"
mt19937_64 rnd(her1);
#include "functional"
const i64 oo = 1e9;
const int maxn = 3e2+5;
IV cmax(i64&x,i64 val){x<val?x=val,0:0;}
i64 n,m,tp1,tp2,u1[maxn],v1[maxn],u2[maxn],v2[maxn],a[maxn];
struct DSU{
	i64 fa[maxn],siz[maxn],mn;
	IV init(){F(i,1,n)siz[fa[i]=i]=1;mn=1;}
	i64 find(i64 x){return fa[x]==x?x:fa[x]=find(fa[x]);}
	IV merge(i64 x,i64 y){
		x=find(x);y=find(y);
		if(x!=y)fa[x]=y,siz[y]+=siz[x];
		mn=min(mn,--siz[y]);
	}
	bool ck(i64 x){
		return mn>=x;
	}
	bool mergeck(i64 x,i64 y,i64 v){
		x=find(x);y=find(y);i64 tmp=siz[y];
		if(x!=y)tmp+=siz[x];return min(mn,--tmp)>=v;
	}
}dsu1,dsu2;
IV add(i64 u){
	dsu1.merge(u1[u],v1[u]);
	dsu2.merge(u2[u],v2[u]);
}
vector<i64>G[maxn];bool vis[maxn],ed[maxn],inq[maxn];
i64 bk[maxn],val[maxn],sum;pair<i64,i64>dis[maxn];
int main(){
	// freopen("1.in","r",stdin);
	// freopen("1.out","w",stdout);
	n=read();m=read();tp1=2-read();tp2=2-read();
	F(i,1,m)u1[i]=read(),v1[i]=read(),u2[i]=read(),v2[i]=read(),a[i]=read();
	F(o,1,m){
		// F(i,1,m)putchar(vis[i]+'0');puts("");
		F(i,1,m)G[i].clear(),bk[i]=ed[i]=inq[i]=0,dis[i]={-oo,0};
		F(i,1,m)if(vis[i]){
			dsu1.init();dsu2.init();
			F(x,1,m)if(vis[x]&&x!=i)add(x);
			F(y,1,m)if(!vis[y]){
				// if(o==4&&i==4&&y==5)cout<<dsu1.mergeck(u1[y],v1[y],tp1)<<endl;

				if(dsu1.mergeck(u1[y],v1[y],tp1))G[i].push_back(y);
				// ,cout<<"add"<<i<<' '<<y<<endl;
				if(dsu2.mergeck(u2[y],v2[y],tp2))G[y].push_back(i);
				// ,cout<<"add"<<y<<' '<<i<<endl;
			}
		}
		F(i,1,m)val[i]=(vis[i]?-a[i]:a[i]);

		dsu1.init();dsu2.init();
		F(i,1,m)if(vis[i])add(i);
		queue<i64>qwq;
		F(i,1,m)if(!vis[i]){
			if(dsu1.mergeck(u1[i],v1[i],tp1))
				bk[i]=0,dis[i]={val[i],-1},qwq.push(i);//,cout<<"?"<<i<<endl;
			if(dsu2.mergeck(u2[i],v2[i],tp2))ed[i]=1;//,cout<<"??"<<i<<endl;
		}
		while(!qwq.empty()){
			i64 u=qwq.front();qwq.pop();inq[u]=0;
			for(i64 v:G[u]){
				pair<i64,i64>nw=make_pair(dis[u].first+val[v],dis[u].second-1);
				if(nw>dis[v]){dis[v]=nw,bk[v]=u;if(!inq[v])qwq.push(v),inq[v]=1;}
			}
		}
		// F(i,1,m)cout<<dis[i].first<<' ';puts("");
		i64 pos=0;
		F(i,1,m)if(ed[i]&&(!pos||dis[pos]<dis[i]))
			pos=i;
		if(dis[pos].first<=0)break;
		sum+=dis[pos].first;
		while(pos)vis[pos]^=1,pos=bk[pos];
	}
	cout<<sum;
	return 0;
}