2019.3 PAT甲级-3 Telefraud Detection (25 分) 并查集

秒速五厘米 2024-04-18 09:25 24阅读 0赞

Telefraud（电信诈骗） remains a common and persistent problem in our society. In some cases, unsuspecting victims lose their entire life savings. To stop this crime, you are supposed to write a program to detect those suspects from a huge amount of phone call records.

A person must be detected as a suspect if he/she makes more than K short phone calls to **different** people everyday, but no more than 20% of these people would call back. And more, if two suspects are calling each other, we say they might belong to the same gang. A makes a **short**phone call to B means that the total duration of the calls from A to B is no more than 5 minutes.

### Input Specification: ###

Each input file contains one test case. For each case, the first line gives 3 positive integers K (≤500, the threshold（阈值） of the amount of short phone calls), N (≤103, the number of different phone numbers), and M (≤105, the number of phone call records). Then M lines of one day's records are given, each in the format:

caller receiver duration

where `caller` and `receiver` are numbered from 1 to N, and `duration` is no more than 1440 minutes in a day.

### Output Specification: ###

Print in each line all the detected suspects in a gang, in ascending order of their numbers. The gangs are printed in ascending order of their first members. The numbers in a line must be separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

If no one is detected, output `None` instead.

### Sample Input 1: ###

5 15 31
    1 4 2
    1 5 2
    1 5 4
    1 7 5
    1 8 3
    1 9 1
    1 6 5
    1 15 2
    1 15 5
    3 2 2
    3 5 15
    3 13 1
    3 12 1
    3 14 1
    3 10 2
    3 11 5
    5 2 1
    5 3 10
    5 1 1
    5 7 2
    5 6 1
    5 13 4
    5 15 1
    11 10 5
    12 14 1
    6 1 1
    6 9 2
    6 10 5
    6 11 2
    6 12 1
    6 13 1

### Sample Output 1: ###

3 5
    6

**Note:** In sample 1, although `1` had 9 records, but there were 7 distinct receivers, among which `5` and `15` both had conversations lasted more than 5 minutes in total. Hence `1` had made 5 short phone calls and didn't exceed the threshold 5, and therefore is not a suspect.

### Sample Input 2: ###

5 7 8
    1 2 1
    1 3 1
    1 4 1
    1 5 1
    1 6 1
    1 7 1
    2 1 1
    3 1 1

### Sample Output 2: ###

None

**题意&思路：**输入阈值k,总人数n,通话记录数量m，之后m行输入x打给y了z分钟。然后输出每个嫌疑人团伙。

x被判定为嫌疑人的条件是，打了>=k通短电话，且<20%k给他回电。

注意题意的5分钟（短电话的时间）是总计通话，不是一通电话的时间。

用二维数组ma存x->y的通话时间，循环一遍记录num是短电话的数量，sum为回电的数量，若满足条件则放入sus中。

此时所有嫌疑人都在sus中了，要判断他们是否为一个团伙就看他们间是否相互通话，用并查集联合他们。

因为要按照字典序输出，所以要再for一遍从最小编号的开始，然后输出与他同父亲的结点。

若sus为空则说明没有嫌疑人，输出None。

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<iostream>
    #include<string>
    #include<sstream>
    #include<algorithm>
    #include<map>
    #include<set>
    #include<queue>
    #include<stack>
    #include<vector>
    using namespace std;
    #define inf 0x3f3f3f3f
    #define LL long long
    vector<int> sus;
    int ma[1005][1005];
    int fa[1005];
    int find(int x)    //查找   
    {  
    	int r=x,i=x,j;
    	while(fa[r]!=r)
    	r=fa[r];
    	while(fa[i]!=i)
    	j=fa[i],fa[i]=r,i=j;
    	return r;
    }
    void combine(int x,int y)
    {
    	int xx=find(x);
    	int yy=find(y);
    	if(xx!=yy)
    	fa[xx]=yy;
    }
    int main()
    {
    	int k,n,m,i,j,x,y,z;
    	memset(ma,0,sizeof ma);
    	scanf("%d%d%d",&k,&n,&m);
    	for(i=0;i<m;i++)
    	{
    		scanf("%d%d%d",&x,&y,&z);
    		ma[x][y]+=z;
    	}
    	for(i=1;i<=n;i++)
    	{
    		int num=0,sum=0;
    		for(j=1;j<=n;j++)
    		{
    			if(i==j)continue;
    			if(ma[i][j]>0&&ma[i][j]<=5)
    			{
    				num++;
    				if(ma[j][i]>0)
    				sum++;
    			}
    		}
    		//cout<<i<<" num: "<<num<<" sum: "<<sum<<endl;
    		if(num>k&&sum*5<=num) 
    		sus.push_back(i);
    	}
    	//for(i=0;i<sus.size();i++)
    	//cout<<sus[i]<<endl;
    	for(i=1;i<=n;i++)
    	fa[i]=i;
    	for(i=0;i<sus.size();i++)
    	{
    		for(j=0;j<sus.size();j++)
    		{
    			if(i==j)continue;
    			if(ma[sus[i]][sus[j]]&&ma[sus[j]][sus[i]])
    			{
    				//cout<<"combine:"<<sus[i]<<" "<<sus[j]<<endl;
    				combine(sus[i],sus[j]);
    			}
    			
    		}
    	}
    	bool vis[1005]={0};
    	for(i=0;i<sus.size();i++)
    	{
    		if(vis[sus[i]]==0)
    		{
    			vis[sus[i]]=1;
    			printf("%d",sus[i]);
    			for(j=0;j<sus.size();j++)
    			{
    				if(vis[sus[j]]==0&&find(sus[i])==find(sus[j]))
    				{
    					vis[sus[j]]=1;
    					printf(" %d",sus[j]);
    				}
    			}
    			printf("\n");
    		}
    	}
    	if(sus.size()==0)
    	printf("None\n");
    }