DSP

UVa 13008 Exposing corruption Latin America Region

2019-07-13 11:03发布

站内文章 / DSP
14704 0 1072
根据rival关系可以构造一个图。对于任意一个连通分量C，如果将其中的x in DSP换到DDP，那么C中DDP的member必须放到DSP中，那么原先在DSP中x以外的member必须放到DDP中。所以每个连通分量只有两种状态，change or not change，change的cost就是连通分量中每个member的price之和，value就是DSP or PPP中人数的改变量（可能<0）。之后再用01背包求解。 #include #include #include #include #include using namespace std; //UVA 13008 - Exposing corruption const int maxn=210; int D; int P; int R; int B; int price[maxn]; vectormp[maxn]; vectorconnected[maxn]; bool vis[maxn]; int connectcnt; int cost[maxn]; int reward[maxn]; int ans; void calconnectedpart(int st,int idx) { queueque; while(!que.empty()) que.pop(); vectorret; ret.clear(); que.push(st); vis[st]=true; while(!que.empty()) { int now=que.front(); que.pop(); ret.push_back(now); for(int i=0;i=0;v--) { if(cost[i]<=v) { f[v]=max(f[v],f[v-cost[i]]+reward[i]); } } } ans=f[B]; } void calDSP() { memset(cost,0,sizeof(cost)); memset(reward,0,sizeof(reward)); for(int i=0;i=1&&people<=D) reward[i]--; else if(people>=D+1&&people<=D+P) reward[i]++; } } } void calPPP() { memset(cost,0,sizeof(cost)); memset(reward,0,sizeof(reward)); for(int i=0;i=1&&people<=D) reward[i]++; else if(people>=D+1&&people<=D+P) reward[i]--; } } } int main() { freopen("input.txt","r",stdin); // freopen("myall.out","w",stdout); while(scanf("%d %d %d %d",&D,&P,&R,&B)!=EOF) { memset(vis,false,sizeof(vis)); memset(mp,0,sizeof(mp)); memset(connected,0,sizeof(connected)); memset(price,0,sizeof(price)); connectcnt=0; ans=0; for(int i=1;i<=D;i++) { scanf("%d",&price[i]); } for(int i=1;i<=P;i++) { scanf("%d",&price[D+i]); } for(int i=0;i

热门文章