西风烈 下载,衢州一中教师招聘,中国梦的手抄报
## 题意
[题目链接](https://www.luogu.org/problemnew/show/p2196)
## sol
早年noip的题锅好多啊。。
这题连有向边还是无向边都没说(~~害的我wa了一遍~~)
直接$f[i]$表示到第$i$个点的贡献
转移的时候枚举从哪个点转移而来
然后我就用一个$n^2$的算法过了一道$n \leqslant 20$的题？？。。
```cpp
#include
#include
#include
using namespace std;
const int maxn = 101;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0'="" ||="" c=""> '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9')="" x="x" *="" 10="" +="" c="" -="" '0',="" c="getchar();" return="" x="" *="" f;="" }="" int="" n,="" a[maxn],="" ca[maxn][maxn],="" f[maxn],="" pre[maxn],="" ed;="" int="" main()="" {="" n="read();" for(int="" i="1;" i=""><= n;="" i++)="" a[i]="read();" for(int="" i="1;" i=""><= n;="" i++)="" for(int="" j="i" +="" 1;="" j=""><= n;="" j++)="" ca[i][j]="ca[j][i]" =="" read();="" int="" ans="0;" for(int="" i="1;" i=""><= n;="" i++)="" {="" for(int="" j="1;" j=""><= i="" -="" 1;="" j++)="" if(ca[i][j]="" &&="" f[j]=""> f[i]) f[i] = f[j], pre[i] = j;
f[i] += a[i];
if(f[i] > ans) ans = f[i], ed = i;
}
vector v;
while(ed) v.push_back(ed), ed = pre[ed];
for(int i = v.size() - 1; i >= 0; i--) printf("%d ", v[i]); puts("");
printf("%d", ans);
return 0;
}
```
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！
点击进行留言回复
相关文章:
-
-
C++ 作用域
作用域：名称在翻译单元（包括文件）的可见范围 局部： 只在定义它的代码块中可用，如自动变量 全局（文件作用域）： 从定义位置到文件结尾都可用 注意： 静...
[阅读全文]
-
-
-
-
聚合类型与POD类型
Lippman在《深度探索C++对象模型》的前言中写道： I have heard a number of people over the years ...
[阅读全文]
-
-
-
-
-
我要评论
网友评论