网站开发 估算 excel,网站建设都有哪些方面,公司网站建设合同电子版,wordpress网站图片丢失正题 题目大意
有nnn个任务#xff0c;完成需要先决条件#xff0c;然后有完成价值。选择一些任务完成#xff0c;求最大价值。 解题思路
首先#xff0c;如果有环#xff0c;那么这些环是不可能完成的。所以先用拓扑排序找环。
然后考虑最大子权闭合图#xff0c;对于…正题 题目大意
有nnn个任务完成需要先决条件然后有完成价值。选择一些任务完成求最大价值。 解题思路
首先如果有环那么这些环是不可能完成的。所以先用拓扑排序找环。
然后考虑最大子权闭合图对于正数点用原点连接而负数点则连接汇点。容量为权值的绝对值。
然后对于每个点连接先决条件。
然后跑最大子权闭合图 codecodecode
#includecstdio
#includequeue
#includecstring
#includealgorithm
using namespace std;
const int N510,inf2147483647/3;
struct node{int to,next,w;
}a[N*N*2];
int n,tot,ls[N],in[N],v[N],ans,dep[N],s,e;
int m[N],edge[N][N];
queueint q;
void addl(int x,int y)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;in[y];
}
void adde(int x,int y,int w)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;a[tot].tox;a[tot].nextls[y];ls[y]tot;a[tot].w0;
}
void top()
{for(int i1;in;i)if(!in[i]) q.push(i);while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;in[y]--;if(!in[y])q.push(y);}}
}
bool bfs()
{memset(dep,0,sizeof(dep));while(!q.empty()) q.pop();q.push(s);dep[s]1;while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(!dep[y]a[i].w){dep[y]dep[x]1;if(ye) return true;q.push(y);}}}return false;
}
int dinic(int x,int flow)
{int rest0,k;if(xe) return flow;for(int ils[x];i;ia[i].next){int ya[i].to;if(dep[x]1dep[y]a[i].w){rest(kdinic(y,min(a[i].w,flow-rest)));a[i].w-k;a[i^1].wk;if(restflow) return flow;}}if(!rest) dep[x]0;return rest;
}
int main()
{scanf(%d,n);for(int i1;in;i){scanf(%d%d,v[i],m[i]);for(int j1;jm[i];j){scanf(%d,edge[i][j]);addl(edge[i][j],i);}}top();memset(ls,0,sizeof(ls));tot1;sn1;en2;for(int i1;in;i){if(in[i]) continue;if(v[i]0) adde(i,e,-v[i]);else adde(s,i,v[i]),ansv[i];for(int j1;jm[i];j){if(in[edge[i][j]]) continue;adde(i,edge[i][j],inf);}}while(bfs())ans-dinic(s,inf);printf(%d,ans);
}
