题目描述
GDOI商场推出优惠活动,以超低价出售若干种商品。但是,商场为避免过分亏本,规定某些商品不能同时购买,而且每种超低价商品只能买一件。身为顾客的你想获得最大的实惠,也就是争取节省最多的钱。经过仔细研究,发现商场出售的超低价商品中,不存在以下情况: n(n>=3)种商品C1,C2,…..,Cn,其中Ci,Ci+1是不能同时购买的(i=1,2…,n-1)并且C1, Cn也不能同时购买。 编程计算可以节省的最大金额数。思路
将每一个点同源点和汇点分别连边,然后将有冲突的点连边,那么最大流的一半就是最小的损失的金额#include
#include
#include
#include
#define maxn 400000
#define min(x,y) x'9'){if (ch=='-')p=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*p;
}
int add(int x,int y,int w)
{
e[++maxE]=(edge){y,w,ls[x]};
ls[x]=maxE;
e[++maxE]=(edge){x,0,ls[y]};
ls[y]=maxE;
}
int bfs(int x)
{
queue t;
t.push(x);
fill(state,0);
state[x]=1;
while (!t.empty())
{
int tt=t.front();t.pop();
for (int i=ls[tt];i;i=e[i].next)
{
if (e[i].w>0&&!state[e[i].y])
{
state[e[i].y]=state[tt]+1;
t.push(e[i].y);
if (e[i].y==E)
return true;
}
}
}
return false;
}
int cur[maxn];
int find(int x,int mn)
{
if (x==E||!mn) return mn;
int ret=0;
for (int &i=cur[x];i;i=e[i].next)
if (state[x]+1==state[e[i].y]&&e[i].w>0)
{
int d=find(e[i].y,min(mn-ret,e[i].w));
e[i].w-=d;
e[i^1].w+=d;
ret+=d;
if (ret==mn) break;
}
return ret;
}
int main()
{
n=read();m=read();
S = 0; E = n * 2 +1;
int tot = 0;
for (int i=1;i<=n;i++)
{
int x=read();
tot += x;
add(S,i,x);
add(i+n,E,x);
}
for (int i=1;i<=m;i++)
{
int x = read(), y =read();
add(x, y + n, INF);
add(y, x + n, INF);
}
int ans=0;
while (bfs(S))
{
for (int i=0;i<=E+maxE;i++)
cur[i]=ls[i];
ans+=find(S,INF);
}
printf("%d\n",tot - ans / 2);
}
f[i][0]表示以i为根的树不选i这个点可以达到的最大价值
f[i][0]表示以i为根的树选i这个点可以达到的最大价值 转移显然 f[now][0]=Σmax(f[son][1],f[son][0])
f[now][1]=w[now]+Σf[son][0]
#include
#define maxn 1001
struct edge
{
int to, next;
}e[maxn];
edge e2[maxn];
int ls[maxn], ls1[maxn], a[maxn], f[maxn][maxn];
bool fl[maxn];
int dfs(int now)
{
fl[now] = 1;
for (int i = ls[now]; i; i = e[i].next)
if (fl[e[i].to] == 0)
{
dfs(e[i].to);
f[now][0] += f[e[i].to][1] > f[e[i].to][0] ? f[e[i].to][1] : f[e[i].to][0];
f[now][1] += f[e[i].to][0];
}
f[now][1] += a[now];
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
int l = 0;
for (int i = 1; i <= m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
e[++l] = (edge) {y, ls[x]};
ls[x] = l;
e[++l] = (edge) {x, ls[y]};
ls[y] = l;
}
int ans = 0;
for (int i = 1; i <= n; i++)
if (!fl[i])
{
dfs(i);
ans += f[i][0] > f[i][1] ? f[i][0] : f[i][1];
}
printf("%d\n", ans);
}
Comments NOTHING