P2428 债务清单 题解

· · 题解

\text{题目传送门}

|

\text{博客}

\text{题目大意}

给你 m 条对 n 个变量的限制，形如 x_a+x_b=c。同时满足 \forall i ,x_i \ge 0 。求 x_1\sim x_n 的值。保留两位小数。无解报告 IMPOSSIBLE。否则保证有唯一解。

\text{Solution}

不妨尝试用 x_1 表示 x_2\sim x_n。

以样例为例子，我们有：

\begin{cases}x_1+x_2=2\\x_2+x_3=4\\x_1+x_3=6\end{cases}

变换一下得到：

\begin{cases}x_1=x_1\\x_2=2-x_1=4-x_3=4-(6-x_1)=x_1-2\\x_3=6-x_1=4-x_2=4-(2-x_1)=x_1+2\end{cases}

所以我们只要存下一个变量的某种表示方法的系数和常数，然后下一次搜到解方程即可。

这里要注意判断无解的情况：

注意可能有多于一个的连通块。

但是不要忘了还有一种特殊情况：若两个变量和为零，那么这两个变量都为零。对于每个连通块，如果有上述情况存在，即可直接更新答案，但要注意检查答案。

对于无解的判断样例参考这篇帖子，之前的题解全部无法通过。

这里我使用 bfs 实现，时间复杂度 \mathcal{O}(n+m)。

\text{Code}

# include <bits/stdc++.h>
using namespace std ; 
const int N = 1e3 + 7 ;
const int M = 1e5 + 7 ;
struct edge {
    int nxt , v , w ;
} e [ M << 1 ] ;  // 双倍内存 
int h [ N ] , cnt ;
inline void add_edge ( int u , int v , int w ) {
    e [ ++ cnt ] = ( edge ) { h[u] , v , w } ;
    h[u] = cnt ;
}
struct node {
    int pos , k , b ; // 系数，常数 
} tmp ;
int k[N] , b[N] ;
double x = -114514 ; // 开始一个不可能的值 
int n , m ; double ans[N] ;
bool vis[N] , vis2[N] , vis3[N] ;
int main () {
    ios :: sync_with_stdio ( false ) , cin . tie ( 0 ) , cout . tie ( 0 ) ;
    cin >> n >> m ;
    for ( int i = 1 ; i <= m ; i ++ ) {
        int u , v , w ; cin >> u >> v >> w ;
        add_edge ( u , v , w ) , add_edge ( v , u , w ) ;
    }
    queue < int > qq ;
    for ( int i = 1 ; i <= n ; i ++ ) {
        if ( vis[i] ) continue ; x = -114514 ;
        bool bo = 0 ; int y ;
        queue < int > c ; c . push ( i ) ;
        while ( ! c . empty () ) { // bfs 求 w = 0 
            int u = c . front () ; c . pop () ; vis2[u] = 1 ;
            for ( int j = h[u] ; j ; j = e[j] . nxt ) {
                int v = e[j] . v , w = e[j] . w ;
                if ( w == 0 ) bo = 1 , y = u ;
                if ( ! vis2[v] ) {
                    vis2[v] = 1 ; 
                    c . push ( v ) ;
                }
            }
        }
        if ( bo == 1 ) {
            queue < int > cc ; cc . push ( y ) ;
            while ( ! cc . empty () ) { // bfs 更新答案 
                int u = cc . front () ; cc . pop () ; vis3[u] = 1 ;
                for ( int j = h[u] ; j ; j = e[j] . nxt ) {
                    int v = e[j] . v , w = e[j] . w ;
                    if ( ans[v] == 0 ) ans[v] = w - ans[u] ; // 更新并 check 
                    else {
                        cout << "IMPOSSIBLE\n" ; // 矛盾 
                        return 0 ;
                    }
                    if ( ! vis3[v] ) {
                        vis3[v] = 1 ;
                        cc . push ( v ) ;
                    }
                }
            }
        } 
        queue < node > q ; tmp = ( node ) { i , 1 , 0 } ; q . push ( tmp ) ;
        while ( ! q . empty () ) {
            node u = q . front () ; q . pop () ; vis [ u . pos ] = 1 ; qq . push ( u . pos ) ;
            if ( k [ u . pos ] == 0 && b [ u . pos ] == 0 ) { // 更新一个新的点 
                k [ u . pos ] = u . k , b [ u . pos ] = u . b ;
                for ( int i = h [ u . pos ] ; i ; i = e[i] . nxt ) {
                    int v = e[i] . v , w = e[i] . w ;
                    node _ = ( node ) { v , - u . k , w - u . b } ; // w - ( kx + b ) = - kx + w - b 
                    q . push ( _ ) ;
                }
            }
            if ( k [ u . pos ] == u . k && b [ u . pos ] != u . b ) { // 无解 
                cout << "IMPOSSIBLE\n" ;
                return 0 ;
            }
            if ( k [ u . pos ] == u . k && b [ u . pos ] == u . b ) continue ; // 无数解 
            double nx = -1.0 * ( b [ u . pos ] - u . b ) / ( k [ u . pos ] - u . k ) ; // 新的答案 
            if ( x == -114514 ) x = nx ; 
            if ( fabs ( x - nx ) > 0.0000001 ) { // 矛盾 
                cout << "IMPOSSIBLE\n" ;
                return 0 ;
            }
        }
        if ( x == -114514 && ! bo ) { // 无数解 
            cout << "IMPOSSIBLE\n" ;
            return 0 ;
        }
        if ( bo ) continue ; // 之前 w = 0 更新过了 
        while ( ! qq . empty () ) { // 更新答案 
            int u = qq . front () ; qq . pop () ;
            ans[u] = k[u] * x + b[u] ;
        }
    } 
    for ( int i = 1 ; i <= n ; i ++ ) {
        if ( ans[i] < 0 ) { // 不能为负 ！！！ 
            cout << "IMPOSSIBLE\n" ;
            return 0 ;
        }
    }
    for ( int i = 1 ; i <= n ; i ++ )
        printf ( "%.2f\n" , ans[i] ) ;
    return 0 ; 
}