傳送門
文章目錄
題意：
給你一張nnn個(gè)點(diǎn)mmm條邊的圖，每個(gè)點(diǎn)都有一個(gè)當(dāng)前值aia_iai?，目標(biāo)值bib_ibi?，每次可以選擇一條邊(i,j)(i,j)(i,j)，將ai,aja_i,a_jai?,aj?都加上任意一個(gè)數(shù)，問最終能否將所有aia_iai?都變成目標(biāo)值。
n,m≤2e5n,m\le2e5n,m≤2e5
思路
我們?cè)O(shè)ci=bi?aic_i=b_i-a_ici?=bi??ai?，sum=∑cisum=\sum c_isum=∑ci?，那么當(dāng)summod2=1sum\bmod 2=1summod2=1的時(shí)候一定無解，因?yàn)槊看涡薷亩际墙osumsumsum加上一個(gè)可正可負(fù)的偶數(shù)，如果sumsumsum為奇數(shù)的話一定是不能變成000的。
讓后通過手玩可以發(fā)現(xiàn)，兩個(gè)點(diǎn)之間路徑長(zhǎng)度為奇數(shù)的時(shí)候，可以將兩個(gè)數(shù)同時(shí)加上kkk，兩個(gè)點(diǎn)之間為偶數(shù)的時(shí)候，可以將某個(gè)位置加上kkk，某個(gè)位置減去kkk。可以想到二分圖染色來將圖分成兩部分。
假設(shè)原圖是一個(gè)二分圖，那么只能在兩邊的集合中同時(shí)加上某個(gè)數(shù)，所以當(dāng)兩個(gè)集合的∑ci\sum c_i∑ci?不相等的時(shí)候，一定無解，否則一定有解。
否則原圖不是一個(gè)二分圖，上面已經(jīng)保證sumsumsum為偶數(shù)了，那么答案一定存在。
判斷二分圖可以用并查集。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<random>
#include<cassert>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].l+tr[u].r)>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-6;int n
,m
;
int p
[N
];
int a
[N
],b
[N
];int find(int x
) {return x
==p
[x
]? x
:p
[x
]=find(p
[x
]);
}int main()
{
int _
; scanf("%d",&_
);while(_
--) {scanf("%d%d",&n
,&m
);LL sum
=0;for(int i
=1;i
<=n
*2;i
++) p
[i
]=i
;for(int i
=1;i
<=n
;i
++) scanf("%d",&a
[i
]);for(int i
=1;i
<=n
;i
++) {int x
; scanf("%d",&x
);x
-=a
[i
]; b
[i
]=x
;sum
+=x
;}for(int i
=1;i
<=m
;i
++) {int a
,b
; scanf("%d%d",&a
,&b
);p
[find(a
)]=find(b
+n
);p
[find(a
+n
)]=find(b
);}sum
=abs(sum
);if(sum
%2==1) {puts("NO");continue;} int flag
=0;for(int i
=1;i
<=n
;i
++) if(find(i
)==find(i
+n
)) flag
=1;if(!flag
) {sum
=0;for(int i
=1;i
<=n
;i
++) if(find(1)==find(i
)) sum
+=b
[i
]; else sum
-=b
[i
];if(sum
==0) puts("YES");else puts("NO");} else puts("YES");}return 0;
}
總結(jié)
以上是生活随笔為你收集整理的Codeforces Round #726 (Div. 2) F. Figure Fixing 二分图 + 思维的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
