【提高组】较复杂图论I

P1113 杂务

*拓扑排序模板。

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
const int M=10005;
queue<int>q;
int n,ans,mx[M],in[M],t[M];
bool e[M][M];
inline void toposort(){
    For(i,1,n){
        if(!in[i]){q.push(i);mx[i]=t[i];}
    }
    while(!q.empty()){
        int u=q.front();q.pop();
        For(i,1,n){
            if(e[u][i]){
                in[i]--;
                if(!in[i]) q.push(i);
                mx[i]=max(mx[i],mx[u]+t[i]);
            }
        }
    }
    For(i,1,n) ans=max(ans,mx[i]);
}
int main(){
    scanf("%d",&n);
    For(i,1,n){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        t[a]=b;
        while(c!=0){
            in[a]++;
            e[c][a]=1;
            scanf("%d",&c);
        }
    }
    toposort();
    printf("%d",ans);
    return 0;
}

*更妙的做法在下面，更考验思维，跟我的想法相似，但实现更妙。

*因为其前驱一定在他之前读入，所以读入任务时每次从其前驱中选一个耗时最长的转移，同时更新最后答案。

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
int n,l,t,ans[10005],maxans,id,tme;
int main(){
    scanf("%d",&n);
    For(i,1,n){
        scanf("%d",&id);
        scanf("%d",&tme);
        int tmp=0;
        while(scanf("%d",&t)&&t) tmp=max(ans[t],tmp);
        ans[id]=tmp+tme;
        maxans=max(ans[i],maxans);
    } 
    printf("%d
",maxans);
    return 0;
 } 

*WA因为心态，题目容易便略加思考就打代码，没去证明正确性&思考代码大概怎么打。

P1268 树的重量

*思维好题，这种无从下手的题一般都手动从n=1,2,3..来发现规律。

*题目有点难懂，抓重点就行了。

*考虑n=2, 则必定为1、2连边，答案就是dis[1][2]；

  考虑n=3, 则必定为1、2连边，3连在1、2的连边上，答案就是dis[1][2]+（dis[1][3]+dis[2][3]-dis[1][2]）/2，画图理解一下。

  考虑n=j , 则枚举i=1~n，len=（dis[i][j]+dis[1][j]-dis[1][i]）/2，j必连在1、i使得len最小的边上，答案则为dis[1][2]+lenj的最小值。

 *代码

#include<bits/stdc++.h>
#define ri register int
#define ll long long
#define For(i,l,r) for(ri i=l;i<=r;i++)
#define Dfor(i,r,l) for(ri i=r;i>=l;i--)
using namespace std;
ll n,len,ans,dis[33][33]; 
inline ll read(){
    ll f=1,sum=0;
    char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){sum=(sum<<1)+(sum<<3)+(ch^48);ch=getchar();}
    return f*sum;
}
inline void write(ll x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int main(){
    n=read();
    while(n){
        For(i,1,n-1){
            For(j,i+1,n){
                dis[i][j]=read();
            }
        }
        ans=dis[1][2];
        For(i,3,n){
             len=1e9;
            for(ri j=2;j<i;j++){
                len=min(len,(dis[1][i]+dis[j][i]-dis[1][j])/2);    
            }
            ans+=len;
        }
        n=read();write(ans);printf("
");
    }
    return 0;
}

 *参考 https://www.luogu.org/blog/user4341/solution-p1