JZOJ3640 COCI2014 题目解答:就是对于整个有向图,求边数最少的正环并且环上长度和要尽可能的大。
N<=300
可以矩阵乘法。
邻接矩阵乘 K 次就是走了 K 步。
那么可以用类似倍增 LCA 的做法
走
找到在哪两个之间然后 Log 逼近
Log M 找到最小的一个满足条件的 K。
注意常数优化。
矩乘
总的复杂度
- #include#include#include#include#include#include#define fo(i, a, b) for (int i = a; i <= b; i++)#define fod(i, a, b) for (int i = a; i >= b; i--)#define INF 1000000000#define LL long long#define N 305int n,
- m,
- s1,
- s2;
- bool bz[N];
- using namespace std;
- struct node {
- int f[N][N];
- friend node operator * (node a, node b) {
- node c;
- fo(i, 1, n) {
- fo(j, 1, n) {
- c.f[i][j] = -INF;
- fo(k, 1, n) {
- int v = a.f[i][k] + b.f[k][j];
- if (v > c.f[i][j]) c.f[i][j] = v;
- }
- }
- }
- return c;
- }
- }
- a[16],
- d,
- d1;
- bool pd(int lq) {
- if (lq == -1) {
- fo(i, 1, n) if (d1.f[i][i] > 0) return 1;
- return 0;
- } else {
- fo(i, 1, n) if (a[lq].f[i][i] > 0) return 1;
- return 0;
- }
- }
- int main() {
- cin >> n >> m;
- fo(i, 1, n) {
- fo(j, 1, n) {
- a[0].f[i][j] = -INF;
- }
- a[0].f[i][i] = 0;
- }
- fo(i, 1, m) {
- int x,
- y,
- p1,
- p2;
- scanf("%d%d%d%d", &x, &y, &p1, &p2);
- a[0].f[x][y] = p2 - p1;
- }
- int k = 0;
- d1 = a[k];
- while (!pd(k)) {
- a[k + 1] = a[k] * a[k];
- k++;
- }
- int k1 = k - 1,
- v = 1 << (k - 1);
- d1 = d = a[k1];
- while (!pd( - 1)) {
- if (k1 > 1) k1--;
- d1 = d * a[k1];
- while (k1 > 0 && pd( - 1)) k1--,
- d1 = d * a[k1];
- v += (1 <
就爱阅读 www.92to.com 网友整理上传, 为您提供最全的知识大全, 期待您的分享,转载请注明出处。
来源: http://www.92to.com/bangong/2017/03-13/18650681.html