树上操作+数学+方程思想 P2428【债务清单】

greenheadstrange · 2019-06-13 10:38:54 · 题解

分析：

看到这道题我还以为是高斯消元，可惜M≤100000，GG

怎么办呢？

先分析样例（如果我们用数学的方法来做的话，我们该怎么做呢？）

1. 先设第一个数为x

2. 然后求出另外两个点的值

3. 再通过方程求得x的值，其它点的值迎刃而解

在回到本题

先设出x，再依次写出其它点的值（kx+b）当有重新返回的时候就可以用方程来求出x的值

for(int k=1;k<=n;k++){
    if(v[k])continue;
        while(!q.empty())q.pop();
        q.push(k);
        f[k]=1;
        v[k]=1;
        b[k]=0;
        while(!q.empty()){
            int x=q.front();
            q.pop();
            for(int i=head[x];i;i=c[i].next){
                int nf=-f[x],nb=c[i].l-b[x],y=c[i].to;
                if(f[y]){
                    if(nf==f[y]&&nb!=b[y]){cout<<"jinitaimei";return 0;}
                    if(nf!=f[y]){ans[k]=(b[y]-nb)/(nf-f[y]);break;}
                }
                else{
                    q.push(y);
                    f[y]=nf;
                    b[y]=nb;
                }
            }
        }
        q.push(k);
        while(!q.empty()){
            int x=q.front();
            q.pop();
            for(int i=head[x];i;i=c[i].next){
                int y=c[i].to;
                if(!v[y]){
                    v[y]=1;
                    ans[y]=c[i].l-ans[x];
                    q.push(y);
                }
            }               
        }
    }

再给个完整的

#include<bits/stdc++.h>
using namespace std;
bool v[1005];
struct note{
    int next,to;
    double l;
}c[200005];
int n,m,cnt,head[1005];
double ans[1005],f[1005],b[1005];
queue<int>q;
void add(int x,int y,int z){
    cnt++;
    c[cnt].l=z;
    c[cnt].to=y;
    c[cnt].next=head[x];
    head[x]=cnt;
}
int main(){
    int aa,bb;
    double cc;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d%d%lf",&aa,&bb,&cc),add(aa,bb,cc),add(bb,aa,cc);
    for(int k=1;k<=n;k++){
        if(v[k])continue;
        while(!q.empty())q.pop();
        q.push(k);
        f[k]=1;
        v[k]=1;
        b[k]=0;
        while(!q.empty()){
            int x=q.front();
            q.pop();
            for(int i=head[x];i;i=c[i].next){
                int nf=-f[x],nb=c[i].l-b[x],y=c[i].to;
                if(f[y]){
                    if(nf==f[y]&&nb!=b[y]){cout<<"jinitaimei";return 0;}
                    if(nf!=f[y]){ans[k]=(b[y]-nb)/(nf-f[y]);break;}
                }
                else{
                    q.push(y);
                    f[y]=nf;
                    b[y]=nb;
                }
            }
        }
        q.push(k);
        while(!q.empty()){
            int x=q.front();
            q.pop();
            for(int i=head[x];i;i=c[i].next){
                int y=c[i].to;
                if(!v[y]){
                    v[y]=1;
                    ans[y]=c[i].l-ans[x];
                    q.push(y);
                }
            }               
        }
    }
    for(int i=1;i<=n;i++)printf("%.2lf\n",ans[i]);
    return 0;
}