开发网站 要网站icp经营许可证吗,城市分类信息网站系统,简述你对于网站建设的认识,建设外贸网站显然先选每个点都取一遍然后再取满次数最优#xff0c;用最小树形图决定第一次取的顺序。 朱刘算法的流程是#xff08;总复杂度O(nm)#xff09;#xff1a; 1.对除根外所有点#xff0c;找到所有指向它的边中权值最小的那一条#xff0c;记其权值为ind[]。 2.找到所有不… 显然先选每个点都取一遍然后再取满次数最优用最小树形图决定第一次取的顺序。 朱刘算法的流程是总复杂度O(nm) 1.对除根外所有点找到所有指向它的边中权值最小的那一条记其权值为ind[]。 2.找到所有不包含根的、由(1)中找到的那些边构成的环并将环缩点。若没有这样的环则结束。 3.将所有缩点后不是自环的边的权值减去边的终点的ind。 主要思路就是贪心调整具体看代码实现。 1 #includecstdio2 #includealgorithm3 #define rep(i,l,r) for (int i(l); i(r); i)4 using namespace std;5 6 const int N61,M21000;7 const double inf1e10;8 int n1,m,m1,n1,x,y,cnt,num[N],pos[N],pre[N],id[N],vis[N];9 double a[N],ans,v,ind[N];
10 struct E{ int u,v; double w; }e[M];
11
12 double Zhuliu(int rt,int n,int m){
13 int tn,tm; double res0;
14 while (1){
15 rep(i,1,n) ind[i]inf,pre[i]id[i]vis[i]0;
16 tntmind[rt]0;
17 rep(i,1,m) if (e[i].wind[e[i].v]) ind[e[i].v]e[i].w,pre[e[i].v]e[i].u;
18 rep(i,1,n){
19 int xi; resind[i];
20 while (x!rt vis[x]!i !id[x]) vis[x]i,xpre[x];
21 if (x!rt !id[x]){
22 id[x]tn;
23 for (int kpre[x]; k!x; kpre[k]) id[k]tn;
24 }
25 }
26 if (!tn) break;
27 rep(i,1,n) if (!id[i]) id[i]tn;
28 rep(i,1,m) if (id[e[i].u]!id[e[i].v]) e[tm](E){id[e[i].u],id[e[i].v],e[i].w-ind[e[i].v]};
29 ntn; mtm; rtid[rt];
30 }
31 return res;
32 }
33
34 int main(){
35 freopen(bzoj4349.in,r,stdin);
36 freopen(bzoj4349.out,w,stdout);
37 scanf(%d,n1);
38 rep(i,1,n1){
39 scanf(%lf%d,v,x);
40 if (x) pos[i]n,e[m](E){1,n,v},a[n]v,num[n]x-1;
41 }
42 scanf(%d,m1);
43 rep(i,1,m1){
44 scanf(%d%d%lf,x,y,v);
45 if (!pos[x] || !pos[y]) continue;
46 e[m](E){pos[x],pos[y],v}; a[pos[y]]min(a[pos[y]],v);
47 }
48 rep(i,2,n) ansa[i]*num[i];
49 printf(%.2lf\n,Zhuliu(1,n,m)ans);
50 return 0;
51 } 转载于:https://www.cnblogs.com/HocRiser/p/10602884.html
