专业深圳网站建设,大理旅游网站建设,站长基地,浙江纸巾包装设计公司正题
题目链接:https://www.luogu.com.cn/problem/P4258 题目大意
给出nnn个球#xff0c;mmm个篮筐#xff0c;每个球都可以被放入一些特定的篮筐#xff0c;每个球都要放#xff0c;要求球的个数小于等于111的篮筐数量最多。 保证有解#xff0c;输出方案。 1≤T≤5,1…正题
题目链接:https://www.luogu.com.cn/problem/P4258 题目大意
给出nnn个球mmm个篮筐每个球都可以被放入一些特定的篮筐每个球都要放要求球的个数小于等于111的篮筐数量最多。 保证有解输出方案。
1≤T≤5,1≤n≤3m,1≤m≤1001\leq T\leq 5,1\leq n\leq 3m,1\leq m\leq 1001≤T≤5,1≤n≤3m,1≤m≤100 解题思路
额其实做题之前已经知道正解是带花树就简单很多了。
每个篮筐我们开一个三个点的环那么如果环上大于一个点呗匹配掉了那么这个环内就无法匹配了。
又因为一定有解所以肯定不会因为环上的匹配使答案更劣所以这样匹配出来的结果为ansansans那么答案就是ans−nans-nans−n。
但是有一个问题我们发现这样跑的话每个球不一定都是匹配点这样会影响我们输出方案。因为我们是找增广路的做法这种做法不会减少已经匹配了的点所以我们如果优先跑球代表的点就不会有问题了。 code
#includecstdio
#includecstring
#includealgorithm
#includequeue
using namespace std;
const int N1010,M2e510;
struct node{int to,next;
}a[M1];
int cnt,tot,T,n,m,e,ans,ls[N];
int dfn[N],pre[N],fa[N],match[N],tag[N];
queueint q;
void addl(int x,int y){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].tox;a[tot].nextls[y];ls[y]tot;return;
}
int find(int x)
{return (fa[x]x)?(x):(fa[x]find(fa[x]));}
int LCA(int x,int y){cnt;xfind(x);yfind(y);while(dfn[x]!cnt){dfn[x]cnt;xfind(pre[match[x]]);if(y)swap(x,y);}return x;
}
void Blossom(int x,int y,int lca){while(find(x)!lca){pre[x]y;ymatch[x];if(tag[y]2){tag[y]1;q.push(y);}fa[x]fa[y]lca;xpre[y];}return;
}
int Agu(int s){memset(tag,0,sizeof(tag));memset(pre,0,sizeof(pre));for(int i1;i3*mn;i)fa[i]i;while(!q.empty())q.pop();q.push(s);tag[s]1;while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(!tag[y]){tag[y]2;pre[y]x;if(!match[y]){for(int uy,lst;u;ulst)lstmatch[pre[u]],match[u]pre[u],match[pre[u]]u;return 1;}tag[match[y]]1;q.push(match[y]);}else if(tag[y]1find(x)!find(y)){int lcaLCA(x,y);Blossom(x,y,lca);Blossom(y,x,lca);}}}return 0;
}
int main()
{scanf(%d,T);while(T--){totans0;memset(ls,0,sizeof(ls));memset(match,0,sizeof(match));scanf(%d%d%d,n,m,e);for(int i1;im;i)addl(i*3-2,i*3-1),addl(i*3-1,i*3),addl(i*3,i*3-2);for(int i1;ie;i){int x,y;scanf(%d%d,x,y);addl(x3*m,y*3);addl(x3*m,y*3-1);addl(x3*m,y*3-2);}for(int in3*m;i1;i--)if(!match[i])ansAgu(i);printf(%d\n,ans-n);for(int i1;in;i)printf(%d ,1(match[3*mi]-1)/3);putchar(\n);}return 0;
}
