Team

時間限制:?1 Sec??內(nèi)存限制:?128 MB
提交:?124??解決:?10
[提交] [狀態(tài)] [命題人:admin]

題目描述

ACM-ICPC is a interesting game. A team takes part in this game must consist of exactly (no more and no less) three players. Every year, many new members will join the FZU ACM team. How to form teams becomes a big problem.
There are 3N members this year. Each member has a power Wi. If three distinct members x, y, z form a team, the power of this team is the minimum value of Wx, Wy, Wz.
There are M pairs of relationship called best friend. If member A and member B are best friend, they must be in the same team.
We want to form N teams, and get the maximum sum of the power of these N teams. Can you help us?

?

輸入

Input is given from Standard Input in the following format:
N M
W1 W2 . . . W3N
A1 B1
.
.
.
AM BM
Constraints
1≤N, M≤103
1≤Wi≤109
1≤Ai, Bi≤3N (1≤i≤M, Ai≠Bi)
All inputs are integers.

?

輸出

If it’s possible to form N teams, print one integer denotes the maximum sum of the power of these N teams. Otherwise print -1.

?

樣例輸入

2 1
1 2 3 4 5 6
3 4

樣例輸出

4

題目大意：

? ? ? 先輸入兩個整數(shù)n和m，代表有n個人，m組朋友關(guān)系，下面一行輸入n個整數(shù)，代表每個人的能力值，然后輸入m行關(guān)系a，b，代表a和b是好朋友，現(xiàn)在要將他們進(jìn)行分隊(duì)，每隊(duì)固定為3個人，并且每隊(duì)的能力值為三個人中最小的能力值，即對于隊(duì)伍1：a,b,c，其隊(duì)伍的能力為w[a]，w[b]，w[c]三者的最小值，同時也規(guī)定如果a和b是朋友關(guān)系，則a,b一定要在同一個隊(duì)伍里，問組成隊(duì)伍的最大能力值之和。

解題思路：

? ? ? ?首先確定的是朋友關(guān)系的一定須在同一個隊(duì)伍里，所以可以先按照朋友關(guān)系先將當(dāng)前的情況分為三種：一人一個隊(duì)，兩人一個隊(duì)，三人一個隊(duì)，因此可以通過并查集來實(shí)現(xiàn)，將為朋友關(guān)系的人放到同一個集合中，并將這個集合的權(quán)值設(shè)為集合中元素能力值的最小值，如果出現(xiàn)了集合中的元素大于3的情況，那么這種情況一定不成立，然后根據(jù)其集合人數(shù)將其分為1人，2人，3人三種情況，分別存在數(shù)組中。

? ? ? dp[i][j]代表的是已經(jīng)在一人集合中選取了i個，在兩人集合中選取了j個，則若要組成一個三人小隊(duì)，可以分為兩種情況，選三個一人隊(duì)，選一個一人一個兩人隊(duì)，因此可以推出動態(tài)轉(zhuǎn)移方程為：

dp[i+3][j]=max(dp[i+3][j],dp[i][j]+min(v[1][i],min(v[1][i+1],v[1][i+2]));

dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+min(v[1][i],v[2][j]));

假設(shè)：一人隊(duì)數(shù)組長度為len1，兩人隊(duì)數(shù)組長度為len2，則我們可以知道若dp[len1][len2]==0，則證明此種情況不成立，組不成全為三人隊(duì)，若其不為0，則用當(dāng)前的dp[len1][len2]加上三人隊(duì)集合的能力值即可。

代碼：

#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> #include <cstdlib> #include <cstring> #include <map> #include <stack> #include <queue> #include <vector> #include <bitset> #include <set> #include <utility> #include <sstream> #include <iomanip> using namespace std; typedef long long ll; typedef unsigned long long ull; #define inf 0x3f3f3f3f #define rep(i,l,r) for(int i=l;i<=r;i++) #define lep(i,l,r) for(int i=l;i>=r;i--) #define ms(arr) memset(arr,0,sizeof(arr)) //priority_queue<int,vector<int> ,greater<int> >q; const int maxn = (int)1e5 + 5; const ll mod = 1e9+7; ll w[3100]; int f[3100]; ll num[3100]; ll dp[3100][3100]; vector<ll> v[10]; bool ju; int find(int x) {return x==f[x]?x:find(f[x]); } void merge(int a,int b) {int fa=find(a);int fb=find(b);if(fa!=fb) {if(fa<fb) {f[fb]=fa;num[fa]=num[fa]+num[fb];w[fa]=min(w[fa],w[fb]);if(num[fa]>3) ju=false;num[fb]=0;}else {f[fa]=fb;num[fb]=num[fb]+num[fa];w[fb]=min(w[fa],w[fb]);if(num[fb]>3) ju=false;num[fa]=0;}} } int main() {#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);#endif//freopen("out.txt", "w", stdout);ios::sync_with_stdio(0),cin.tie(0);int n,m;cin>>n>>m;rep(i,1,3*n) {cin>>w[i];f[i]=i;num[i]=1;}ju=true;rep(i,1,m) {int a,b;cin>>a>>b;merge(a,b);}if(ju==false) {cout<<"-1"<<endl;return 0;}rep(i,1,3*n) {if(num[i]==1) v[1].push_back(w[i]);if(num[i]==2) v[2].push_back(w[i]);if(num[i]==3) v[3].push_back(w[i]);}int len1=v[1].size();int len2=v[2].size();int len3=v[3].size();sort(v[1].begin(),v[1].end());sort(v[2].begin(),v[2].end());sort(v[3].begin(),v[3].end());v[1].push_back(0);v[1].push_back(0);v[1].push_back(0);v[1].push_back(0);v[2].push_back(0);v[2].push_back(0);v[2].push_back(0);v[2].push_back(0);for(int i=0;i<=len1;i++) {for(int j=0;j<=len2;j++) {dp[i+3][j]=max(dp[i+3][j],dp[i][j]+v[1][i]);dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+min(v[1][i],v[2][j]));}}if(dp[len1][len2]!=0) {ll ans=dp[len1][len2];for(int i=0;i<len3;i++) ans+=v[3][i];cout<<ans<<endl;}else {cout<<"-1"<<endl;}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的【并查集+dp】Team的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。