Regional Changchun Online-Plays

8581 ワード
URL:http://acm.hdu.edu.cn/showproblem.php?pid=5438
ポズ
Time Limit：1500/1000 MS（Java/Others）    Memory Limit:13131313137272 K(Java/Others)Total Submission(s)：376    Acceepted Submission(s)：116
Problem Description
Betty owns a lot of ponds，some of them are connected with other ponds by pipes，and there will not be more thone pipe between two ponds.Each pond has a value
v.
Now Betty Wants to remove some ponds because she does not have enough money.But each time when she removes a pond，she can remove the ponds which are connected with less thand wow
Note that Betty.shuld keep removing ponds untilのmore ponds can be removed.After that，please help he cacalculate the sum of the value for each connected component consisting of a odnumber of ponds
 
Input
The first line of input will contain a number
T(1≦T≦30)which is the number of test cases.
For each test case，the first line contains two number separated by a blank.One is the number
p(1≦p≦104)which represents the number of ponds she owns，and the other is the number
m(1≦m≦105)which represents the number of pipes.
The nextラインcontains
p numbers
v 1,…，vp，where
vi(1≦vi≦108)indicating the value of pond
i.
Each of the last
mラインcontain two numbers
a and
b，which indicates that pond
a and pond
b are connected by a pipe.
 
Output
For each test case、output the sum of the value of all connected components consisting of odd number of ponds after removing all the ponds connected with less than two pipes.
 
Sample Input

   
   
   
   

    
    
    
    1
7 7
1 2 3 4 5 6 7
1 4
1 5
4 5
2 3
2 6
3 6
2 7
 
Sample Output

   
   
   
   

    
    
    
    21
 
ソurce
2015 ACM/ICPC Asia Regional Changchun Online
 
Recommund
hujie   |   We have carefully selected several simiar probles for you:   5449  5448  5447  5446  5445
子供の数が1以下の点を列に入れて、この点につながる子供の数を修正して、列を維持して、最後にdfsを通して池の数を調べて、奇数はプラスして、偶数は無視します。
考えはいいようですが、最初は間違えて題意を理解しました。当時はodd number of pondsの意味がよく分かりませんでした。ですから、最初はdfsがありませんでした。
本当に祭りの時間ですね。終わる前に何回も開けましたが、ずっとWRに戻りました。その後はREになりました。原因が分かりません。やはり最後にこの問題を落としました。
終わってから少しずつ間違えました。コードが乱れていますので、全然間違いを見つけられませんでした。その後、PSの助けで二つの恥ずべきエラーを見つけました。最初のREはチームに入ってから削除する時に使ったのは列の中の現在の点の子供の数です。結果はこの数は入隊後に修正されるかもしれません。（判断が終わったら、配列ノードの値が変わりますので）、実際にはもうエッジがないかもしれません。このようにして、resultはend()に戻るかもしれませんので、削除時にはerase(end()は間違いです。
もう一つはもっとSBです。最後にdfs図の時にnをmに使ってもいいですか？
エラーコード:
#pragma comment(linker, "/STACK:102400000000,102400000000")
#include<iostream>
#include<stdio.h>
#include<math.h>
#include <string>
#include<string.h>
#include<map>
#include<queue>
#include<set>
#include<utility>
#include<vector>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define eps 1e-8
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define ll long long int
#define mod 1000000007
#define maxn 1005
#define maxm 1000005
int  point[10005];
struct T{
  int childnum;
  int i;
  int mark;
  vector <int> vec;
  friend bool operator < (T n1, T n2)
  {
    return n1.childnum > n2.childnum;
  }
}node[10005];

bool vis[10005];
int cnt=0;
long long tsum=0;
void dfs(int x){
    if(vis[x]==true) return ;
    cnt++,tsum += point[ x ];
    vis[x]=true;
    for(int i=0;i<node[x].childnum;i++)
      dfs( node[x].vec[i] );
}


int main (){
int Case;
rd(Case);
while(Case--){
    memset(vis,0,sizeof(vis));
    int n,m,temp1,temp2;
    ll sum=0;
    vector<int>::iterator  result;
    rd2(n,m);
    for(int i=1;i<=n;i++) node[i].childnum=0,node[i].i=i,node[i].mark=0 ,node[i].vec.clear();
    for(int i=1;i<=n;i++){
        rd(point[i]);
        sum+=point[i];
    }
    for(int i=0;i<m;i++){
        rd2(temp1,temp2);
        //bool mark = (find( node[temp1].vec.begin(), node[temp1].vec.end(), temp2 ) == node[temp1].vec.end() );

        if(temp1!=temp2){
          node[temp1].vec.push_back(temp2);
          node[temp1].childnum++;
          node[temp2].vec.push_back(temp1);
          node[temp2].childnum++;
        }
    }
    priority_queue <T> que;
    for(int i=1;i<=n;i++)
        if(node[i].childnum<=1){
           que.push(node[i]);
           node[i].mark=1;
           sum-=point[i];
        }
    //cout<<"***"<<endl;
    while(!que.empty()){
       // cout<<"&&&"<<que.top().i<<endl;
        if(que.top().childnum==1){     //     ：  node[que.top().i].childnum==1 
            int x=que.top().vec[0];//cout<<x<<endl;
            result = find( node[x].vec.begin(), node[x].vec.end(), que.top().i );
            node[x].vec.erase(result);
            node[x].childnum--;

            int i = que.top().i ;
            node[i].vec.erase(node[i].vec.begin());
            node[i].childnum-- ;

            if(node[x].childnum<=1 && node[x].mark == 0){
                que.push(node[x]);
                node[x].mark=1;
                sum-=point[x];
            }
        }
        que.pop();
    }
     for(int i=1;i<=m;i++){  ///    ：  i<=n
        tsum=cnt=0;
        if(!vis[i] && node[i].childnum>=1 ){
            dfs(i);
            if(  cnt%2==0 )
             sum-=tsum;
        }
        // cout<<endl;
     }
    printf("%I64d
",sum);
}

return 0 ;
}
実際には、その時点では、自分のコードを見た後に、ほとんどの塊の糞は、思考の根本的な明確されていないので、いくつかのアイデアの後にコードをノックしても、少し霧が残っていますので、将来のアイデアを持って、少なくとも全体的な脈絡はほぼクリアされています。
#pragma comment(linker, "/STACK:102400000000,102400000000")
#include<iostream>
#include<stdio.h>
#include<math.h>
#include <string>
#include<string.h>
#include<map>
#include<queue>
#include<set>
#include<utility>
#include<vector>
#include<algorithm>
#include<stdlib.h>
using namespace std;
#define eps 1e-8
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define ll long long int

int  point[10005];
vector <int> vec[10005];
bool vis[10005];
bool inqueue[10005];
int cnt=0;
long long tsum=0;


void dfs(int x)
{
    if(vis[x]) return ;
    cnt++,tsum += point[ x ],vis[x]=true;
    for(int i=0; i<vec[x].size(); i++)
        dfs( vec[x][i] );
}

void addedge(int temp1,int temp2)
{
    vec[temp1].push_back(temp2);
    vec[temp2].push_back(temp1);
}

int main ()
{
    int Case;
    rd(Case);
    while(Case--)
    {
        memset(vis,0,sizeof(vis));
        memset(inqueue,0,sizeof(inqueue));
        int n,m,temp1,temp2;
        ll sum=0;
        vector<int>::iterator result;
        rd2(n,m);
        for(int i=1; i<=n; i++)
        {
            vec[i].clear();
            rd(point[i]);
            sum+=point[i];
        }
        for(int i=0; i<m; i++)
        {
            rd2(temp1,temp2);
            addedge(temp1,temp2);
        }

        queue <int> que;   ///                   
        for(int i=1; i<=n; i++)
            if(vec[i].size()<=1)
            {
                que.push(i);
                vis[i]=true,inqueue[i]=1,sum-=point[i];
            }

        while(!que.empty())
        {
            if( vec[que.front()].size()==1 )
            {
                int x=vec[que.front()][0];
                result = find(  vec[x].begin(), vec[x].end(), que.front() );
                vec[x].erase(result);

                vec[que.front()].clear(); ///            

                if(vec[x].size()<=1 && inqueue[x] == 0)
                {
                    que.push(x);
                    inqueue[x]=1,vis[x]=true,sum-=point[x];
                }
            }
            que.pop();
        }

        for(int i=1; i<=n; i++){
            tsum=cnt=0;
            if( !vis[i] ){
                dfs(i);
                if(  cnt%2==0 )
                    sum-=tsum;
            }
        }
        printf("%I64d
",sum);
    }

    return 0 ;
}
列の中の要素を遍歴している時は、端の関係を削除する必要はありません。すでに入隊の時に後のdfsのために準備しましたので、入隊してからは遍歴しなくなります。削除しても大丈夫です。vec[i]の数を変更すればいいです。
実は最初の考えがはっきりしたらAはとっくに落ちていますので、これからは注意してください。
プロジェクトの真夜中のあたまは、Invalid character found in method name.HTTP method names must be tokens the HTTP protocoを間違えました。
maven使用例