B3600 Solution

· · 题解

题目传送门

最初是在整理 B 题库的时候发现了这道题，一直想做却又没做，今天终于 AC，也刚好让这题通过数达到 555，遂写一篇题解纪念一下。

当然也有知识盲区，所以一部分参考了网上关于图论的知识点，勿喷。

思路比较简单但是代码很长，共 130 行。

\textbf{Part.1 邻接矩阵或权矩阵}

用 vis 数组标记重边，如果遇到重边则不输出，否则把这条边设为出现过，然后如果该图是赋权图就把 a_{u_i,v_i} 设为边权 w_i，否则就设为 1。注意如果该图是无向图还需要反向建边。最后如果该图没有重边就输出 a。

\textbf{Part.2 关联矩阵}

如果该图是赋权图或者该图有自环则不输出，用 f 标记。然后如果该图是有向图就把起点 b_{u_i,i} 设为 1，把终点 b_{v_i,i} 设为 -1，如果该图是无向图就把 b_{u_i,i} 和 b_{v_i,i} 都设为 1，也就是都看作起点。最后如果该图没有自环又不是赋权图就输出 b。

\textbf{Part.3 邻接表}

用 vector 存储，构造图 G 和图 J，后续的逆向表也会用到，然后对于每条边，把 \{v,w\} 加入 G_u，把 \{u,w\} 加入 J_v，然后如果该图是无向图还需要反向建边。最后输出 G，如果该图是赋权图还需要输出边权。

\textbf{Part.4/5 正向表/逆向表}

正向表的 Ax 向量相当于前缀和，也就是规定向量 Ax_1=1，那么 Ax_{i+1}=Ax_i+|G_i|，其中 |G_i| 表示 G_i 的长度。然后用 Bx 向量保存结点 u 连接的所有结点，Cx 存储权值，都从图 G 里取出就可以了。最后输出，如果该图是赋权图那么输出 Cx，赋权图也是一样的操作，只不过是从 J 里取出结点和边权，注意如果该图是无向图则不输出逆向表。

\textbf{Part.6 完整代码}

#include <iostream>
#include <vector>
#define F first
#define S second
using namespace std;

const int N = 1005;

bool t1, t2;
int n, m, u[N], v[N], w[N];
int a[N][N], b[N][N], cur;
int Ax[N], Bx[N], Cx[N];
int Ay[N], By[N], Cy[N];
bool f = true, vis[N][N];
vector<pair<int, int> > G[N], J[N];

int main()
{
    // Input.
    cin >> n >> m >> t1 >> t2;
    for (int i = 1; i <= m; i++)
    {
        cin >> u[i] >> v[i];
        if (t2) cin >> w[i];
    }
    // Part.1
    for (int i = 1; i <= m; i++)
    {
        if (vis[u[i]][v[i]]) f = false; // 重边 
        else
        {
            vis[u[i]][v[i]] = true; // 标记为出现过 
            if (t2) a[u[i]][v[i]] = w[i]; // 权矩阵 
            else a[u[i]][v[i]] = 1; // 邻接矩阵 
        }
        if (!t1) // 无向图 
        {
            if (t2) a[v[i]][u[i]] = w[i]; // 权矩阵 
            else a[v[i]][u[i]] = 1; // 邻接矩阵 
        }
    }
    if (f)
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                cout << a[i][j] << " \n"[j == n];
    }
    // Part.2
    f = !t2; // 赋权图 
    for (int i = 1; i <= m; i++)
    {
        if (u[i] == v[i]) f = false; // 自环 
        if (t1) // 有向图 
        {
            b[u[i]][i] = 1; // 起点 
            b[v[i]][i] = -1; // 终点 
        }
        else b[u[i]][i] = b[v[i]][i] = 1; // 无向图都设为 1 
    }
    if (f)
    {
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                cout << b[i][j] << " \n"[j == m];
    }
    // Part.3
    for (int i = 1; i <= m; i++)
    {
        G[u[i]].push_back(make_pair(v[i], w[i])); // 加边 
        J[v[i]].push_back(make_pair(u[i], w[i])); // 反图，逆向表会用到 
        if (!t1) // 无向图 
        {
            G[v[i]].push_back(make_pair(u[i], w[i])); // 加边 
            J[u[i]].push_back(make_pair(v[i], w[i])); // 反图，逆向表会用到 
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < (int)G[i].size(); j++)
        {
            cout << G[i][j].F << " ";
            if (t2) cout << G[i][j].S << " "; // 边权 
        }
        cout << "\n";
    }
    // Part.4
    Ax[1] = 1; // 初值 
    for (int i = 1; i <= n; i++)
    {
        Ax[i + 1] = Ax[i] + (int)G[i].size(); //类似前缀和 
        for (int j = 0; j < (int)G[i].size(); j++)
        {
            Bx[++cur] = G[i][j].F; // 保存邻接表的结点 
            if (t2) Cx[cur] = G[i][j].S; // 权值 
        }
    }
    for (int i = 1; i <= n + 1; i++)
        cout << Ax[i] << " \n"[i == n + 1];
    for (int i = 1; i <= cur; i++)
        cout << Bx[i] << " \n"[i == cur];
    if (t2) // 赋权图输出边权 
    {
        for (int i = 1; i <= cur; i++)
            cout << Cx[i] << " \n"[i == cur];
    }
    // Part.5
    Ay[1] = 1, cur = 0; // 初值 
    for (int i = 1; i <= n; i++)
    {
        Ay[i + 1] = Ay[i] + (int)J[i].size(); // 类似前缀和 
        for (int j = 0; j < (int)J[i].size(); j++)
        {
            By[++cur] = J[i][j].F; // 保存邻接表的结点 
            if (t2) Cy[cur] = J[i][j].S; // 权值 
        }
    }
    if (t1) // 有向图 
    {
        for (int i = 1; i <= n + 1; i++)
            cout << Ay[i] << " \n"[i == n + 1];
        for (int i = 1; i <= cur; i++)
            cout << By[i] << " \n"[i == cur];
        if (t2) // 赋权图输出边权 
        {
            for (int i = 1; i <= cur; i++)
                cout << Cy[i] << " \n"[i == cur];
        }
    }
    return 0;
}