using namespace std;
int n,m,i,j;
int a[5001],b[5001][3];
int f[5001][2];
bool q[5001][2][5001];
void ff(int x,int y){
for(j=1;j<=n;j++){q[i][x][j]=q[i-1][y][j];}
}
int main(){
cin>>n>>m;
memset(f,0,sizeof(f));
memset(q,0,sizeof(q));
for(i=1;i<=n;i++)cin>>a[i];
for(i=1;i<=m;i++){cin>>b[i][0]>>b[i][1]>>b[i][2];}
for(i=1;i<=m;i++){
if(f[i-1][0]<f[i-1][1])
{f[i][0]=f[i-1][1];ff(0,1);}
else
{f[i][0]=f[i-1][0];ff(0,0);}
if((f[i-1][0]+b[i][2]-a[b[i][0]]*(1-q[i-1][0][b[i][0]])-a[b[i][1]]*(1-q[i-1][0][b[i][1]]))<(f[i-1][1]+b[i][2]-a[b[i][0]]*(1-q[i-1][1][b[i][0]])-a[b[i][1]]*(1-q[i-1][1][b[i][1]])))
{f[i][1]=(f[i-1][1]+b[i][2]-a[b[i][0]]*(1-q[i-1][1][b[i][0]])-a[b[i][1]]*(1-q[i-1][1][b[i][1]]));ff(1,1);}
else
{f[i][1]=(f[i-1][0]+b[i][2]-a[b[i][0]]*(1-q[i-1][0][b[i][0]])-a[b[i][1]]*(1-q[i-1][0][b[i][1]]));ff(1,0);}
q[i][1][b[i][0]]=1;q[i][1][b[i][1]]=1;
cout<<f[i][0]<<f[i][1]<<endl;
}
cout<<max(f[m][0],f[m][1]);
system("pause");
return 0;
}
本题我用了01背包的思想，用数组q记录每次动规后的中转站建成情况（0代表没建，1代表建了）
样例过了
然而
。。。。。。。。。
测试结果1: 测试结果错误.错误结果为:0
正确结果应为:68
测试结果2: 测试结果错误.错误结果为:26
正确结果应为:157
测试结果3: 测试结果错误.错误结果为:6
正确结果应为:890
测试结果4: 测试结果错误.错误结果为:20
正确结果应为:787
测试结果5: 测试结果错误.错误结果为:170
正确结果应为:1623
测试结果6: 测试结果错误.错误结果为:113
正确结果应为:688
测试结果7: 测试结果错误.错误结果为:86
正确结果应为:1312
测试结果8: 测试结果错误.错误结果为:25
正确结果应为:271
测试结果9: 测试结果错误.错误结果为:25
正确结果应为:32646
测试结果10: 测试结果错误.错误结果为:25
正确结果应为:29752
这个帖我都发过一遍了，无人响应
一道最大流...
构图：
s到每个基地塔连一个边，容量为成本，每个用户群到t连一个边容量为利润，然后依赖关系连边，容量为正无穷~~
最后的答案就是所有用户群的利润总和减去最大流~~
发下我的程序，最大闭合权子图
话说几天前还很纠结，看不会呢
program profit;
const inf=maxlongint shr 1;
type node1=record
x,y,f,next,op:longint;
end;
var n,m,i,s,t,p,tot,sum,cost,tmp,a,b,c,head,tail:longint;
bian:array[-5..350000]of node1;
first,le,tfirst:array[-5..60000]of longint;
q:array[-5..500000]of longint;
procedure connect(aa,bb,cc:longint);
begin
inc(tot);
with bian[tot] do
begin
x:=aa; y:=bb; f:=cc;
next:=first[x];
first[x]:=tot;
op:=tot+1;
end;
inc(tot);
with bian[tot] do
begin
x:=bb; y:=aa; f:=0; //注意是0！！！！
next:=first[x];
first[x]:=tot;
op:=tot-1;
end;
end;
function bfs:boolean;
var i,k:longint;
begin
for i:=1 to t+5 do begin
le[i]:=inf;
tfirst[i]:=first[i];
end;
head:=0; tail:=1; q[1]:=s; le[s]:=0;
repeat
inc(head);
k:=first[q[head]];
while k<>0 do
with bian[k] do
begin
if (f>0)and(le[x]+1<le[y]) then
begin
le[y]:=le[x]+1;
if y=t then exit(true);
inc(tail);
q[tail]:=y;
end;
k:=next;
end;
until head=tail;
exit(false);
end;
function min(xx,yy:longint):longint;
begin
if xx>yy then exit(yy)
else exit(xx);
end;
function dfs(x,ff:longint):longint;
var tf,k,tmp:longint;
begin
if x=t then exit(ff);
tf:=0;
k:=tfirst[x];
while k<>0 do
with bian[k] do
begin
tfirst[x]:=k;
if (f>0)and(le[y]=le[x]+1) then
begin
tmp:=dfs(y,min(f,ff));
if tmp>0 then begin
inc(tf,tmp);
dec(ff,tmp);
dec(f,tmp);
inc(bian[op].f,tmp);
if ff<=0 then break;
end;
end;
k:=next;
end;
exit(tf);
end;
begin
assign(input,'profit.in');
assign(output,'profit.out');
reset(input); rewrite(output);
readln(n,m);
s:=n+m+2; t:=n+m+1;
tot:=0;
for i:=1 to n do
begin
read(p);
connect(i,t,p);
end;
readln;
for i:=1 to m do
begin
readln(a,b,c);
sum:=sum+c;
connect(s,i+n,c);
connect(i+n,a,inf);
connect(i+n,b,inf);
end;
cost:=0;
while bfs do
begin
tmp:=dfs(s,inf);
while tmp>0 do
begin
cost:=cost+tmp;
tmp:=dfs(s,inf);
end;
end;
sum:=sum-cost;
writeln(sum);
close(input); close(output);
end.