内存限制。内存限制。约翰家一共发N个草场。

时光限定:10000ms

岁月范围:10000ms

题面:

描述

暑假到了!!小Hi以及小Ho为了体验生活,来到了艾在特别草原的约翰家。今天一早,约翰以有事要下,就拜托小Hi和小Ho忙帮放牧。

约翰家一共来N个草场,每个草场有容量也W[i]的牧草,N个草场之间时有发生M条单向的途径。

小Hi与小Ho需要用牛羊群赶到草场上,当她们凭着得了一个草场牧草后,继续去其他草场。当没有得以到的草场或是能够到的草场都已给吃才了后,小hi和小Ho就管牛羊群赶回家。

一样开始小Hi和小Ho在1哀号草场,在回家前,牛羊多最多克吃少多少牧草?

推个例子:

图被每个点表示一个草场,上一些数字代表编号,下局部代表草场的牧草数量w。

于1凭着罢草之后,小Hi与小Ho可以选将牛羊群赶到2要么3,假要小Hi和小Ho把牛羊多到2:

吃得了草场2从此,只能够及草场4,当4凭着了后没可以抵达的草场,所以小Hi和小Ho就把牛羊群赶回家。

倘若选择打1至3,则可到达5,6:

分选5之语句,吃了后只能一直回家。若选择6,还可以重经6回至3,再到5。

所以该图可以选的门道发生3久:

1->2->4 total: 11 
1->3->5 total: 9 
1->3->6->3->5: total: 13

因此极多会吃到之牧草数量也13。

主题改编自USACO月赛金组

提醒:强连通分量

输入

第1推行:2单刚整数,N,M。表示点之多少N,边的数量M。1≤N≤20,000, 1≤M≤100,000

第2履:N个正整数,第i只整数表示第i独牧场的草量w[i]。1≤w[i]≤100,000

第3..M+2行:2只刚整数,u,v。表示是同样久由u到v的单纯为路。1≤u,v≤N

输出

第1实践:1独整数,最多会吃到之牧草数量。

样例输入 
6 6 
2 4 3 5 4 4 
1 2 
2 4 
1 3 
3 5 
3 6 
6 3 
样例输出 
13

单点时限:1000ms

单点时限:1000ms

约思路:

本条开要一个缩点的操作,也就是说在基础的tarjan算法上,需要加一个数组(程序中凡是sccno),其意思是:如果是属分量,则sccno[i]的价值是以此培训的根本节点,也就算是可由此这个数组知道属于哪个联通分量。 
故总体题之长河尽管是优先跑同任何tarjan,然后因sccno的音讯新建一个贪图,然后还新建的希冀及走同方方面面dfs,最后扫一全体glass数组,求一个max输出就得了。

内存限制:256MB

内存限制:256MB

代码:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=2e4+7;
 4 vector<int> g[maxn];
 5 vector<int> newp[maxn];
 6 int dfn[maxn],low[maxn],w[maxn],glass[maxn],sccno[maxn];
 7 int idx=0;
 8 bool visit[maxn];
 9 stack<int> s;
10 void tarjan(int u)
11 {
12     dfn[u]=low[u]=++idx;
13     s.push(u);
14     visit[u]=true;
15     int v;
16     for(int i=0;i<g[u].size();++i){
17         v=g[u][i];
18         if(dfn[v]==0){
19             tarjan(v);
20             low[u]=min(low[u],low[v]);
21         }else if(visit[v])
22             low[u]=min(low[u],dfn[v]);
23     }
24     if(dfn[u]==low[u])
25         do{
26             v=s.top();
27             s.pop();
28             sccno[v]=u;//指向根节点
29             visit[v]=false;
30         }while(u!=v);
31 }
32 
33 void suodian(int n)
34 {
35     int v,u;
36     for(int i=1;i<=n;++i){
37         for(int j=0;j<g[i].size();++j){
38             u=g[i][j];
39             if(sccno[i]==u)
40                 continue;
41             if(w[u]==0)
42                 continue;
43             if(u!=sccno[u]){
44                 w[sccno[u]]+=w[u];//缩点时将值累加
45                 w[u]=0;
46             }else
47                 newp[sccno[i]].push_back(u);//为了让连通分量连接的边成功接上根节点
48         }
49     }
50 }
51 void dfs(int x,int last)
52 {
53     int v;
54     glass[x]=max(glass[x],glass[last]+w[x]);
55     for(int i=0;i<newp[x].size();++i){
56         v=newp[x][i];
57         if(w[v]!=0&&visit[v]==false){
58             visit[v]=true;
59             dfs(v,x);
60             visit[v]=false;
61         }
62     }
63 }
64 
65 int main()
66 {
67     ios::sync_with_stdio(false);
68     //freopen("in.txt","r",stdin);
69     int n,m,u,v;
70     memset(dfn,0,sizeof(dfn));
71     memset(glass,0,sizeof(glass));
72     cin>>n>>m;
73     for(int i=1;i<=n;++i)
74         cin>>w[i];
75     for(int i=1;i<=m;++i){
76         cin>>u>>v;
77         g[u].push_back(v);
78     }
79     for(int i=1;i<=n;++i)
80         sccno[i]=i;
81     tarjan(1);
82     for(int i=1;i<=n;++i)
83         if(dfn[i]==0)
84             w[i]=0;
85     suodian(n);
86     int ans=0;
87     memset(visit,false,sizeof(visit));
88     visit[1]=true;
89     dfs(1,1);
90     for(int i=1;i<=n;++i)
91         ans=max(ans,glass[i]);
92     cout<<ans<<endl;
93     return 0;
94 }

 

描述

小Ho:喂不得了啦,那边便利店的薯片半价了!

小Hi:啥?!

小Ho:那边的便利店在打折促销啊。

小Hi:走走走,赶紧去看=v=

乃小Hi和小Ho来到了便利店。

老板为了促销,推出了组合包的花样,将不同数额之各项货物从包改成一个成,顾客得挑选组合展开打。比如2袋薯片,1任可乐的重组要5首批,而1兜子薯片,2听可乐的结合要4头版。

透过了解老板,小Hi以及小Ho知道:一共有N种不同之货物及M种不同的商品组合;每一个结缘的价相当组合内商品售价的与,一个结合内一样桩商品不会见过10件。

小Hi:这样到底下来的话,一听可乐就是1首批,而平等承保薯片是2首位。小Ho,如果您了解有的咬合情况,你能够分别算有各个一样桩货物单独的标价也?

小Ho:当然可以了,这样的粗题目怎么能够难及自家啊?

   

提示:高斯消元

 

描述

小Ho:喂不得了呀,那边便利店之薯片半价了!

小Hi:啥?!

小Ho:那边的便利店在打折促销啊。

小Hi:走走走,赶紧去看看=v=

于是小Hi和小Ho来到了便利店。

老板为促销,推出了组合包的款式,将不同数量之各商品由包改成一个结,顾客可选取做展开选购。比如2袋薯片,1放任可乐的组合而5最先,而1口袋薯片,2听可乐的组成而4状元。

由此摸底老板,小Hi和小Ho知道:一共发生N种不同的货与M种不同之货色组合;每一个整合的价位相当于组合内货物售价的同,一个组合内同样起货物不见面越10宗。

小Hi:这样到底下来的话,一听可乐就是1首先,而相同保薯片是2最先。小Ho,如果你知道有的三结合情况,你可知分别算有各个一样码商品单独的价位么?

小Ho:当然好了,这样的稍问题怎么能难及自我哉?

   

提示:高斯消元

 

输入

第1推行:2只刚刚整数,N,M。表示商品之数码N,组合的数量M。1≤N≤500, N≤M≤2*N

第2..M+1行:N+1独非负整数,第i+1行第j排列表示在第i单组成被,商品j的数a[i][j]。第i+1行第N+1独数表示该组合的售价c[i]。0≤a[i][j]≤10,
0≤c[i]≤10^9

输入

第1执行:2独刚整数,N,M。表示商品之数据N,组合的数量M。1≤N≤500, N≤M≤2*N

第2..M+1行:N+1独非负整数,第i+1行第j排列表示于第i单组成中,商品j的多少a[i][j]。第i+1行第N+1个数表示该做的售价c[i]。0≤a[i][j]≤10,
0≤c[i]≤10^9

输出

万一没辙计算起每个商品单独的标价,输出”No solutions”

设可能在多独例外的结果,输出”Many solutions”

使有唯一可能的结果,输出N行,每行一个非负整数,第i实践表示第i单商品单独的售价。数据保证如果有唯一排,那么散一定正是非负整数解。

样例输入

2 2
2 1 5
1 2 4

样例输出

2

1

当下坑爹oj没多少,害的我打了因上午,

修比较简单,高斯消元的沙盘题,

注意eps要开double类型的

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=1001;
 7 const double eps =1e-7;
 8 typedef double Matrix[MAXN][MAXN] ;
 9 inline void read(int &n)
10 {
11     char c=getchar();bool flag=0;n=0;
12     while(c<'0'||c>'9') c=='-'?flag==1,c=getchar():c=getchar();
13     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();
14 }
15 int n,m;
16 Matrix a;
17 double t[MAXN];
18 void Gauss()
19 {
20     int r;
21     for(int i=1;i<=n;i++)// 枚举每一行 
22     {
23         r=i;
24         for(int j=m;j>=i+1;j--)// 枚举后面的行 
25             fabs(a[j][i])>fabs(a[r][i])?r=j:r=r;
26         if(r!=i)    swap(a[r],a[i]); 
27         if(r==i&&fabs(a[i][i])<eps)        printf("Many solutions"),exit(0);
28             
29         for(int j=i+1;j<=m;j++)// 行 
30         {
31             for(int k=n+1;k>i;k--)// 列 
32                 a[j][k]-=(a[j][i]/a[i][i])*a[i][k];
33             a[j][i]=0;
34         }
35     }
36     
37     for(int i=n,j;i<=m;i++)
38     {
39         for(j=1;j<=n;j++)        if(fabs(a[i][j])>eps)        break;
40         if(j==n+1&&fabs(a[i][n+1])>eps)        
41             printf("No solutions\n"),exit(0);
42     }// 是否有解 
43     
44     for(int i=n;i>=1;i--)// 枚举行 
45     {
46         for(int j=i+1;j<=n;j++)// 枚举列 
47             a[i][n+1]-=a[i][j]*a[j][n+1];
48         a[i][n+1]/=a[i][i];
49     }
50     for(int i=1;i<=n;i++)
51         printf("%d\n",(int)(a[i][n+1]+0.5));
52 }
53 int main()
54 {
55     freopen("a.in","r",stdin);
56     freopen("c.out","w",stdout);
57     read(n);read(m);
58     for(int i=1;i<=m;i++)
59         for(int j=1;j<=n+1;j++)
60             scanf("%lf",&a[i][j]);
61     Gauss();
62     
63     return 0;
64 }

 

    

输出

万一无艺术计算产生每个商品单独的价,输出”No solutions”

要可能是多单不等的结果,输出”Many solutions”

一旦有唯一可能的结果,输出N行,每行一个非负整数,第i履行代表第i个商品单独的售价。数据保证如果在唯一排,那么排除一定正是非负整数解。

样例输入

2 2
2 1 5
1 2 4

样例输出

2

1

就坑爹oj没多少,害的我打了因上午,

书写比较简单,高斯消元的沙盘题,

注意eps要开double类型的

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=1001;
 7 const double eps =1e-7;
 8 typedef double Matrix[MAXN][MAXN] ;
 9 inline void read(int &n)
10 {
11     char c=getchar();bool flag=0;n=0;
12     while(c<'0'||c>'9') c=='-'?flag==1,c=getchar():c=getchar();
13     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();
14 }
15 int n,m;
16 Matrix a;
17 double t[MAXN];
18 void Gauss()
19 {
20     int r;
21     for(int i=1;i<=n;i++)// 枚举每一行 
22     {
23         r=i;
24         for(int j=m;j>=i+1;j--)// 枚举后面的行 
25             fabs(a[j][i])>fabs(a[r][i])?r=j:r=r;
26         if(r!=i)    swap(a[r],a[i]); 
27         if(r==i&&fabs(a[i][i])<eps)        printf("Many solutions"),exit(0);
28             
29         for(int j=i+1;j<=m;j++)// 行 
30         {
31             for(int k=n+1;k>i;k--)// 列 
32                 a[j][k]-=(a[j][i]/a[i][i])*a[i][k];
33             a[j][i]=0;
34         }
35     }
36     
37     for(int i=n,j;i<=m;i++)
38     {
39         for(j=1;j<=n;j++)        if(fabs(a[i][j])>eps)        break;
40         if(j==n+1&&fabs(a[i][n+1])>eps)        
41             printf("No solutions\n"),exit(0);
42     }// 是否有解 
43     
44     for(int i=n;i>=1;i--)// 枚举行 
45     {
46         for(int j=i+1;j<=n;j++)// 枚举列 
47             a[i][n+1]-=a[i][j]*a[j][n+1];
48         a[i][n+1]/=a[i][i];
49     }
50     for(int i=1;i<=n;i++)
51         printf("%d\n",(int)(a[i][n+1]+0.5));
52 }
53 int main()
54 {
55     freopen("a.in","r",stdin);
56     freopen("c.out","w",stdout);
57     read(n);read(m);
58     for(int i=1;i<=m;i++)
59         for(int j=1;j<=n+1;j++)
60             scanf("%lf",&a[i][j]);
61     Gauss();
62     
63     return 0;
64 }

 

    

相关文章