本文主要是介绍Codeforces Round #599 (Div. 1) C. Sum Balance（图+dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://codeforces.com/contest/1242/problem/C
具体做法参照题解，记录一个子集当中dp的方法
https://cp-algorithms.com/algebra/all-submasks.html
代码：
#include<bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN=5005;
const int MAXM=(1<<15)+5;
ll sum[20];
bool vis[MAXN*15],ok[MAXM];
int x[16][MAXN],n[20],num[MAXN*15],pos[MAXN*15],stk[MAXN*15],dp[MAXM],pre[MAXM],l[16],r[16];
int top=0;
map<ll,int> id;
vector<int> E[MAXN*15],sv[MAXM];
void dfs(int now,int st)
{if(vis[now]){int cir=0;for(int i=top;i>=1;i--){cir|=(1<<pos[stk[i]]);if(stk[i]==now) break;}if(!ok[cir]){ok[cir]=true;for(int i=top;i>=1;i--){sv[cir].pb(stk[i]);if(stk[i]==now) break;}}return ;}if(st&(1<<pos[now])) return ;st|=(1<<pos[now]);vis[now]=true;stk[++top]=now;for(int v:E[now]){dfs(v,st);}vis[now]=false;top--;
}
int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int k,idx=0;ll S=0;scanf("%d",&k);for(int i=0;i<k;i++){scanf("%d",&n[i]);for(int j=1;j<=n[i];j++){scanf("%d",&x[i][j]);id[x[i][j]]=++idx;num[idx]=x[i][j];pos[idx]=i;sum[i]+=x[i][j];S+=x[i][j];}}if(S%k!=0) return 0*puts("NO");S/=k;for(int i=1;i<=idx;i++){ll v=S-(sum[pos[i]]-num[i]);if(id.find(v)!=id.end()){E[i].pb(id[v]);}}for(int i=1;i<=idx;i++)dfs(i,0);dp[0]=1;for(int i=0;i<(1<<k);i++){if(dp[i]){int rest=i^((1<<k)-1);for(int j=rest;j;j=(j-1)&rest){if(ok[j]){dp[i|j]=1;pre[i|j]=i;}}}}if(!dp[(1<<k)-1]) return 0*puts("NO");int now=(1<<k)-1;while(now){int x=now-pre[now];for(int i:sv[x]){int v=S-(sum[pos[i]]-num[i]);l[pos[id[v]]]=v;r[pos[id[v]]]=pos[i]+1;}now=pre[now];}puts("YES");for(int i=0;i<k;i++)printf("%d %d\n",l[i],r[i]);return 0;
}
这篇关于Codeforces Round #599 (Div. 1) C. Sum Balance（图+dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
