| 购物问题 |
| 难度级别：C； 运行时间限制：1000ms； 运行空间限制：51200KB； 代码长度限制：2000000B |
试题描述 |
由于换季，ACM商场推出优惠活动，以超低价格出售若干种商品。但是，商场为避免过分亏本，规定某些商品不能同时购买，而且每种超低价商品只能买一件。身为顾客的你想获得最大的实惠，也就是争取节省最多的钱。经过仔细研究过，我们发现，商场出售的超低价商品中，不存在以下这种情况：N(3<=n)种商品C1,C2,…,Cn，其中Ci和Ci+1是不能同时购买的(i=1,2,…,n-1)，而且C1和Cn也不能同时购买。请编程计算可以节省的最大金额数。 |
输入 |
第1行两个整数K,M(1<=k<=1000)，其中K表示超低价商品数，K种商品的编号依次为1,2,…,K；M表示不能同时购买的商品对数。接下来K行，第i行有一个整数Xi表示购买编号为i的商品可以节省的金额(1<=Xi<=100)。再接下来M行，每行两个数A和B，表示A和B不能同时购买，1<=A<=K，1<=B<=K，A≠B。 |
输出 |
仅一个整数，表示能节省的最大金额数。 |
输入示例 |
3 1 1 1 1 1 2 |
输出示例 |
2 |
其他说明 |
ssf校内训练 |
题解：好水的题，赤裸裸的二分图。。。（虽然本意是想考DP吧。。。但我们有高级货啊。。。= =）
二分图补集转换的思想不唠叨了，别忘了最大流建模的时候上两条边最后再除以二。
跟501一样瞎搞就好了= =
同时，这次“惨痛”的教训告诉我们，抄最大流模板的时候记得改addedge，我太傻了...
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define PAU putchar(' ')
#define ENT putchar('\n')
using namespace std;
const int maxn=+,maxm=+,inf=-1u>>;
struct ISAP{
struct tedge{int x,y,w,next;}adj[maxm];int ms,fch[maxn];
int gap[maxn],s[maxn],cur[maxn],d[maxn],S,T,top,n;
void init(int n){
this->n=n;ms=;top=;
memset(fch,-,sizeof(fch));
memset(d,-,sizeof(d));
return;
}
void addedge(int u,int v,int w){
adj[ms]=(tedge){u,v,w,fch[u]};fch[u]=ms++;
adj[ms]=(tedge){v,u,,fch[v]};fch[v]=ms++;
return;
}
void bfs(){
queue<int>Q;Q.push(T);d[T]=;
while(!Q.empty()){
int u=Q.front();Q.pop();
for(int i=fch[u];i!=-;i=adj[i].next){
int v=adj[i].y;
if(d[v]==-) d[v]=d[u]+,Q.push(v);
}
} return;
}
int maxflow(int S,int T){
this->S=S;this->T=T;bfs();int k=S,i,flow=;
for(i=;i<=n;i++) cur[i]=fch[i],gap[d[i]]++;
while(d[S]<n){
if(k==T){
int mi=inf,pos;
for(i=;i<top;i++) if(adj[s[i]].w<mi) mi=adj[s[i]].w,pos=i;
for(i=;i<top;i++) adj[s[i]].w-=mi,adj[s[i]^].w+=mi;
flow+=mi;top=pos;k=adj[s[top]].x;
}
for(i=cur[k];i!=-;i=adj[i].next){
int v=adj[i].y;
if(adj[i].w&&d[k]==d[v]+){cur[k]=i;k=v;s[top++]=i;break;}
}
if(i==-){
int lim=n;
for(i=fch[k];i!=-;i=adj[i].next){
int v=adj[i].y;
if(adj[i].w&&d[v]<lim) lim=d[v],cur[k]=i;
} if(--gap[d[k]]==) break;
d[k]=lim+;gap[d[k]]++;
if(k!=S) k=adj[s[--top]].x;
}
} return flow;
}
}sol;
inline int read(){
int x=,sig=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') sig=-;ch=getchar();}
while(isdigit(ch)) x=*x+ch-'',ch=getchar();
return x*=sig;
}
inline void write(int x){
if(x==){putchar('');return;}if(x<) putchar('-'),x=-x;
int len=,buf[];while(x) buf[len++]=x%,x/=;
for(int i=len-;i>=;i--) putchar(buf[i]+'');return;
}
void init(){
int n=read(),m=read();sol.init((n<<)+);
int S=(n<<)+,T=(n<<)+,tot=;
for(int i=;i<=n;i++){
int cur=read();tot+=cur;
sol.addedge(S,i,cur);
sol.addedge(i+n,T,cur);
}
while(m--){
int x=read(),y=read();
sol.addedge(x,y+n,inf);
sol.addedge(y,x+n,inf);
}
write(tot-(sol.maxflow(S,T)>>));
return;
} void work(){
return;
}
void print(){
return;
}
int main(){
init();work();print();return ;
}
搜索
复制