bzoj48834886图论新高度！！！！！

Description

在一个n*m的棋盘上要放置若干个守卫。对于n行来说&＃xff0c;每行必须恰好放置一个横向守卫&＃xff1b;同理对于m列来说&＃xff0c;每列

必须恰好放置一个纵向守卫。每个位置放置守卫的代价是不一样的&＃xff0c;且每个位置最多只能放置一个守卫&＃xff0c;一个守卫

不能同时兼顾行列的防御。请计算控制整个棋盘的最小代价。

Sample Output

19

HINT
在(1,1),(2,2),(3,1)放置横向守卫&＃xff0c;在(2,1),(1,2),(3,3),(2,4)放置纵向守卫。

题解&＃xff1a;假如把a[i][j]看作i->j的边&＃xff0c;那么得到的显然会是一个环套树森林。

那么就跑最小生成树&＃xff0c;然后记录每个点所在连通块是树还是图即可。

假如要合并i,j

如果ij都是图了&＃xff0c;那么就没办法咯。

不然&＃xff0c;i,j在同一个集合时加入这条边即可树->图 &＃xff1b; 不在同一个集合的话&＃xff0c;就把他们并起来&＃xff0c;然后判断得到的是一个什么图形。

如果原来是树&＃43;树&＃xff0c;得到树&＃xff0c;树&＃43;图得到图。
最终就相当于在n&＃43;m个点组成的图中&＃xff0c;找n&＃43;m条边&＃xff0c;组成一个最小环。

复杂度nmlog(nm)

#include using namespace std; typedef long long ll; int pre[100010],c,n,m,vis[100010]; void init(){for(int i&＃61;1;i<&＃61;n&＃43;m;i&＃43;&＃43;)pre[i]&＃61;i;} int findd(int x) {if(x&＃61;&＃61;pre[x])return x;return pre[x]&＃61;findd(pre[x]); } struct node{int a,b,c,next;}edge[200010];int cnt&＃61;0; void add(int a,int b,int c){edge[cnt].a&＃61;a;edge[cnt].b&＃61;b;edge[cnt&＃43;&＃43;].c&＃61;c;} bool cmp(node p1,node p2){return p1.cint main() {scanf("%d%d",&n,&m);init();for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)for(int j&＃61;1;j<&＃61;m;j&＃43;&＃43;){scanf("%d",&c);add(i,j&＃43;n,c);}sort(edge,edge&＃43;cnt,cmp);ll ans&＃61;0,sum&＃61;0;;for(int i&＃61;0;i}
bzoj4886

我们对于a&＃xff0c;b离散后建点&＃xff0c;那么一个卡片就相当于a到b有一条边。

现在要给边定向&＃xff0c;使得每个点入度均为1。&＃xff08;并查集的操作&＃xff09;

贡献&＃61;每个点出度*该点权值

bzoj4883的时候谈过&＃xff0c;这样的连通块要么是环套树要么是树。

肯定都有的一部分贡献是(deg[i]-1)*a[i]&＃xff08;总度数-入度&＃xff09;*权值

对于树&＃xff0c;存在一个节点没有入度&＃xff0c;所以我们并查集的时候找到连通块中权值最大的即可。

对于环套树&＃xff0c;每个点都必须有入度&＃xff0c;那么就直接统计。

#include using namespace std; typedef long long ll; typedef pairP; const int mod&＃61;1e9&＃43;7; const int INF&＃61;0x3f3f3f3f; const ll INFF&＃61;0x3f3f3f3f3f3f3f3f; const double pi&＃61;acos(-1.0); const double eps&＃61;1e-9; ll a[250010],b[250010],node[500010],pre[500010],maxx[500010],num[500010],vis[500010]; int findd(int x) {if(x&＃61;&＃61;pre[x])return x;return pre[x]&＃61;findd(pre[x]); } int main() {int n;scanf("%d",&n);int cnt&＃61;1;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){scanf("%lld%lld",&a[i],&b[i]);node[cnt&＃43;&＃43;]&＃61;a[i],node[cnt&＃43;&＃43;]&＃61;b[i];}sort(node&＃43;1,node&＃43;cnt);int cntt&＃61;2;for(int i&＃61;2;i}