題目鏈接：點擊查看

題目大意：給出一張無向圖，問能否刪除任意數量的邊，使得每個點的度數都達到指定的數值，度數的取值范圍為 [ 1 , 2 ]

題目分析：hdu的原題的弱化版https://blog.csdn.net/qq_45458915/article/details/107305865

代碼：
?

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=1e3+100;const int M=N*N*2;int x[N],y[N],du[N],id[N][N];int n,m,que[M],ql,qr,pre[N],tim=0;struct edge {int v,nxt; }e[M];int h[N],tot=0;int match[N],f[N],tp[N],tic[N];int find(int x) {return f[x]==x?f[x]:f[x]=find(f[x]); }void addedge(int u,int v) {e[++tot]=(edge){v,h[u]};h[u]=tot; }int lca(int x,int y) {for (++tim;;swap(x,y)) if(x) {x=find(x);if(tic[x]==tim) return x; else {tic[x]=tim;x=pre[match[x]];}} }void shrink(int x,int y,int p) {while(find(x)!=p) {pre[x]=y;y=match[x];if(tp[y]==2) {tp[y]=1;que[++qr]=y;}if(find(x)==x) f[x]=p;if(find(y)==y) f[y]=p;x=pre[y];} }bool aug(int s) {for(int i=1;i<=n;++i) f[i]=i;memset(tp,0,sizeof tp);memset(pre,0,sizeof pre);tp[que[ql=qr=1]=s]=1; // 1: type A ; 2: type Bint t=0;while(ql<=qr) {int x=que[ql++];for(int i=h[x],v=e[i].v;i;i=e[i].nxt,v=e[i].v) {if(find(v)==find(x)||tp[v]==2) continue; if(!tp[v]) {tp[v]=2;pre[v]=x;if(!match[v]) {for(int now=v,last,tmp;now;now=last) {last=match[tmp=pre[now]];match[now]=tmp,match[tmp]=now;}return true;} tp[match[v]]=1,que[++qr]=match[v];} else if(tp[v]==1) {int l=lca(x,v);shrink(x,v,l);shrink(v,x,l);}}} return false; }int solve() {int ans=0;for(int i=1;i<=n;i++)if(!match[i]&&aug(i))ans++;return ans; }void init() {tot=0;memset(id,0,sizeof(id));memset(match,0,sizeof(match));memset(tic,0,sizeof(tic));memset(h,0,sizeof(h)); }void build() {int cnt=0;for(int i=1;i<=n;i++)for(int j=1;j<=du[i];j++)id[i][j]=++cnt;for(int i=1;i<=m;i++){addedge(cnt+1,cnt+2);addedge(cnt+2,cnt+1);for(int j=1;j<=du[x[i]];j++){addedge(id[x[i]][j],cnt+1);addedge(cnt+1,id[x[i]][j]);}for(int j=1;j<=du[y[i]];j++){addedge(cnt+2,id[y[i]][j]);addedge(id[y[i]][j],cnt+2);}cnt+=2;}n=cnt; }int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);while(scanf("%d%d",&n,&m)!=EOF){init();int sum=0;for(int i=1;i<=n;i++){scanf("%d",du+i);sum+=du[i];}for(int i=1;i<=m;i++)scanf("%d%d",x+i,y+i);build();if(sum&1)puts("No");else if(solve()*2==n)puts("Yes");elseputs("No");}return 0; }

?

總結

以上是生活随笔為你收集整理的牛客多校 - 1 or 2(一般图最大匹配)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。