首页 > ACM题库 > HDU-杭电 > HDU 4467-Graph[解题报告]HOJ
2015
07-16

HDU 4467-Graph[解题报告]HOJ

Graph

问题描述 :

P. T. Tigris is a student currently studying graph theory. One day, when he was studying hard, GS appeared around the corner shyly and came up with a problem:
Given a graph with n nodes and m undirected weighted edges, every node having one of two colors, namely black (denoted as 0) and white (denoted as 1), you’re to maintain q operations of either kind:
* Change x: Change the color of xth node. A black node should be changed into white one and vice versa.
* Asksum A B: Find the sum of weight of those edges whose two end points are in color A and B respectively. A and B can be either 0 or 1.
P. T. Tigris doesn’t know how to solve this problem, so he turns to you for help.

输入:

There are several test cases.
For each test case, the first line contains two integers, n and m (1 ≤ n,m ≤ 105), where n is the number of nodes and m is the number of edges.
The second line consists of n integers, the ith of which represents the color of the ith node: 0 for black and 1 for white.
The following m lines represent edges. Each line has three integer u, v and w, indicating there is an edge of weight w (1 ≤ w ≤ 231 – 1) between u and v (u != v).
The next line contains only one integer q (1 ≤ q ≤ 105), the number of operations.
Each of the following q lines describes an operation mentioned before.
Input is terminated by EOF.

输出:

There are several test cases.
For each test case, the first line contains two integers, n and m (1 ≤ n,m ≤ 105), where n is the number of nodes and m is the number of edges.
The second line consists of n integers, the ith of which represents the color of the ith node: 0 for black and 1 for white.
The following m lines represent edges. Each line has three integer u, v and w, indicating there is an edge of weight w (1 ≤ w ≤ 231 – 1) between u and v (u != v).
The next line contains only one integer q (1 ≤ q ≤ 105), the number of operations.
Each of the following q lines describes an operation mentioned before.
Input is terminated by EOF.

样例输入:

4 3
0 0 0 0
1 2 1
2 3 2
3 4 3
4
Asksum 0 0
Change 2
Asksum 0 0
Asksum 0 1
4 3
0 1 0 0
1 2 1
2 3 2
3 4 3
4
Asksum 0 0
Change 3
Asksum 0 0
Asksum 0 1

样例输出:

Case 1:
6
3
3
Case 2:
3
0
4

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define N 100005
using namespace std;
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<int,LL> PIL;

int gg[2][2] = {0,1,1,2};
char s[20];
vector<PIL> vec[N];
vector<PIL> vv[N];
int color[N];
LL sum[3], f[3][N];

struct Eg{
    int l, r ,val;
    Eg(){}
    Eg(int _l,int _r,int _val){l=_l;r=_r;val=_val;}
    bool operator <(const Eg&o)const{
        if(l==o.l) return r<o.r;
        return l<o.l;
    }
} e[N<<2];

int main(){
    int cal=0, n, m, i, iter, l, r, v, u;
    LL val;
    while(scanf("%d%d",&n,&m)!=EOF){
        printf("Case %d:\n", ++cal);
        for(i=1;i<=n;i++){
            vec[i].clear();
            vv[i].clear();
            scanf("%d",&color[i]);
        }
        for(i=0;i<m;i++){
            scanf("%d%d%d",&e[i<<1].l,&e[i<<1].r,&e[i<<1].val);
            e[i<<1|1] = Eg(e[i<<1].r,e[i<<1].l,e[i<<1].val);
        }
        sort(e,e+m*2);

        LL tot=e[0].val;
        for(i=1;i<2*m;i++){
            if(e[i].l==e[i-1].l && e[i].r==e[i-1].r) tot+=e[i].val;else{
                vec[e[i-1].l].pb(mp(e[i-1].r,tot));
                tot = e[i].val;
            }
        }
        vec[e[i-1].l].pb(mp(e[i-1].r,tot));

        memset(f,0,sizeof(f));
        memset(sum,0,sizeof(sum));
        for(i=1;i<=n;i++)
        for(iter=0;iter!=vec[i].size();++iter){
            v = vec[i][iter].first;
            val = vec[i][iter].second;
            if(vec[v].size()<vec[i].size() ||(vec[v].size()==vec[i].size() && i<v)){
                sum[gg[color[i]][color[v]]] += val;
                f[color[v]][i] += val;
            }
            else
                vv[i].pb(mp(v,val));
        }

        int Q;
        scanf("%d",&Q);
        while(Q--){
            scanf("%s",s);
            if(s[0]=='A'){
                scanf("%d%d",&l,&r);
                printf("%I64d\n",sum[gg[l][r]]);
            }
            else {
                scanf("%d",&u);
                int col;
                for(col=0;col<=2;col++){
                    sum[gg[color[u]][col]] -= f[col][u];
                    sum[gg[1-color[u]][col]] += f[col][u];
                }
                for(i=0;i<vv[u].size();i++){
                    v =vv[u][i].first;
                    val = vv[u][i].second;
                    f[color[u]][v] -= val;
                    f[1-color[u]][v] += val;
                    sum[gg[color[u]][color[v]]] -=val;
                    sum[gg[1-color[u]][color[v]]] += val;
                }
                color[u] = 1-color[u];
            }
        }
    }
    return 0;
}


/*
4 3
0 1 0 0
1 2 1
2 3 2
3 4 3
4
Change 3
Asksum 0 1
*/