T2
总体思路：先求简单问题，通过修正值来求最小
代码如下：
#include<cctype> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std;int n,T; LL Time_limit,Time_psecond; struct matrix { LL a[55][55]; matrix(){memset(a,0xcf,sizeof(a));} }x,now,f,ans; inline LL read() { char c;LL d=1,f=0; while(c=getchar(),!isdigit(c)) if(c==‘-‘) d=-1;f=(f<<3)+(f<<1)+c-48; while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48; return d*f; } matrix operator *(matrix a,matrix b) { matrix c; for(register int i=0;i<n;i++) for(register int j=0;j<n;j++) for(register int k=0;k<n;k++) c.a[i][j]=max(c.a[i][j],a.a[i][k]+b.a[k][j]); return c; } matrix ksm(matrix c,matrix x,LL y) { for(;y;y>>=1,x=x*x) if(y&1) c=c*x; return c; } signed main() { freopen("k.in","r",stdin); freopen("k.out","w",stdout); T=read(); while(T--) { n=read();Time_psecond=read();Time_limit=read(); memset(f.a,0xcf,sizeof(f.a)); for(register int i=0;i<n;i++) for(register int j=0;j<n;j++) { x.a[i][j]=read(); if(x.a[i][j]==1000) x.a[i][j]=-1e16; } for(register int i=0;i<n;i++) f.a[i][i]=0; for(register int i=1;i<=Time_psecond;i++) f=f*x; now=f; memset(ans.a,0xcf,sizeof(ans.a));ans.a[0][0]=0; for(register int i=0;i<n;i++) now.a[i][i]=max(now.a[i][i],0ll); ans=ksm(ans,now,Time_limit); if(ans.a[0][1]<-1e11) puts("IMPOSSIBLE");else printf("%lld\n",ans.a[0][1]); } }
https://xxyqwq.blog.csdn.net/article/details/110006873
发现是线性的递推式子，并且常数巨大，立刻想到适用矩阵来进行优化，优化的艺术就出现了，因为两次转移是相似的，我们定义出了全新的运算
c.a[i][j]=max(c.a[i][j],a.a[i][k]+b.a[k][j]);
这样子转移的前提是我们ksm的时候也是这个样子转移才会方便，
具体思路如下：
注意坑点：因为是求最大，所以为了判断无解，初始memset都要变成0xcf,然后对于特殊状态一一设置
以上
T4：
#include <stdio.h> #include <algorithm> #include <cstring> #include <cctype> #define lson (k<<1) #define rson (k<<1|1) #define mid ((l+r)>>1) using namespace std; const int maxn=1000200; int l[maxn],L[maxn],n,m;int tot1,tot2; int ru[maxn],que[maxn],w[maxn<<2]; int f[maxn],g[maxn]; struct node { int nex,ver; } e[maxn],E[maxn]; int read() { int x=0,b=1;char c=getchar(); while(!isdigit(c)) b=c==‘-‘?-1:1,c=getchar(); while(isdigit(c)) x=x*10+c-‘0‘,c=getchar(); return x*b; } void topsort() { int hh=1,tt=0; for(int i=1;i<=n;i++) if(!ru[i]) que[++tt]=i; while(hh<=tt) { // printf("%d",hh); int x=que[hh]; for(int i=l[x];i;i=e[i].nex)//?¨￠11¨??¨°¨¤?¨|¨o?????à? { if(--ru[e[i].ver]==0) que[++tt]=e[i].ver; } hh++; } // printf("i\n"); for(int i=1;i<=n;i++) { int x=que[i]; for(int j=l[x];j;j=e[j].nex) f[e[j].ver]=max(f[e[j].ver],f[x]+1);//óéóúê?ó?3?±??üD?μ?￡??ùò??μf′?′￠μ?2?ê???μ?μ?×?3¤?·μ??μ } for(int i=n;i>=1;i--) { int x=que[i]; for(int j=L[x];j;j=E[j].nex) g[E[j].ver]=max(g[E[j].ver],g[x]+1); } return; } void add(int x,int d,int k,int l,int r) { //printf("%d %d %d \n",k,l,r); //if(k==-1) return; if(l==r) { w[k]+=d;return; } if(mid>=x) add(x,d,lson,l,mid);else add(x,d,rson,mid+1,r); w[k]=w[lson]+w[rson]; return; } int ask(int k,int l,int r) { if(l==r) return l; if(w[rson]) return ask(rson,mid+1,r);else return ask(lson,l,mid); } void push(int x){add(x,1,1,0,n);} void pop(int x){add(x,-1,1,0,n);} int main() { freopen("graph.in","r",stdin); freopen("graph.out","w",stdout); n=read();m=read(); for(int i=1;i<=m;i++) { int u,v;u=read();v=read();ru[v]++; e[++tot1]=(node){l[u],v};l[u]=tot1;//zhuyi E[++tot2]=(node){L[v],u};L[v]=tot2; } topsort(); // for(int i=1;i<=n;i++) printf("%d %d\n",f[i],g[i]); for(int i=1;i<=n;i++) push(g[i]); int ans=maxn,id=0; for(int i=1;i<=n;i++) { int x=que[i]; pop(g[x]); for(int j=L[x];j;j=E[j].nex) pop(f[E[j].ver]+g[x]+1);//?¨1?a??¨o??y?¨°topD¨°???¨′?ê?|ì?¨o?¨o??¤???¨°|ì???|¨¤¨a int now=ask(1,0,n); // printf("%d\n",now); if(now<ans) ans=now,id=x; for(int j=l[x];j;j=e[j].nex) push(g[e[j].ver]+f[x]+1); push(f[x]); } printf("%d %d\n",id,ans); }
原文：https://www.cnblogs.com/ILHYJ/p/14035479.html
