3 条题解

  • 1
    @ 2023-7-24 21:04:24
    /*****************************************
    备注:
    ******************************************/
    #include <queue>
    #include <math.h>
    #include <stack>
    #include <stdio.h>
    #include <iostream>
    #include <vector>
    #include <iomanip>
    #include <string.h>
    #include <algorithm>
    using namespace std;
    #define LL long long
    const int N = 2e6 + 10;
    const int INF = 0x3f3f3f3f;
    LL head[N] , to[N],w[N],ne[N],idx=0;
    LL vis[N] , dis[N] ,num[N];
    inline void add(int x,int y , int z)
    {
    	to[++idx] = y;
    	w[idx] = z;
    	ne[idx] = head[x];
    	head[x] = idx;
    }
    LL n , k;
    LL spfa()
    {
    	memset(dis,-0x3f, sizeof dis);
    	stack<int> p;
    	dis[n+1] = 0;
    	vis[n+1] = 1;
    	num[n+1] = 1;
    	p.push(n+1);
    
    	while( !p.empty())
    	{
    		int t = p.top();
    		p.pop();
    		vis[t] = 0;
    		for(int i = head[t] ; i ; i = ne[i])
    		{
    			int u = to[i];
    			if(dis[u] < dis[t] + w[i])
    			{
    				dis[u] = dis[t] + w[i];
    				if(!vis[u]) 
    				{
    					p.push(u);
    					vis[u] = 1;
    					if(++num[u] >= n) 
    						return -1;
    				}
    			}
    		}
    	}
    
    	LL sum = 0;
    	for(int i = 1 ; i <= n+1 ; i++)
    		sum += dis[i];
    	return sum;
    }
    int main()
    {
    	cin >> n >> k;
    	for(int i = 0 ; i < k ; i++)
    	{
    		int z,x,y;
    		scanf("%d%d%d",&z,&x,&y);
    		if(z == 1)
    			add (x,y,0),add (y,x,0);
    		else if ( z == 2)
    			add(x,y,1);
    		else if( z == 3)
    			add(y,x,0);
    		else if(z == 4)
    			add(y,x,1);
    		else if(z ==5)
    			add(x,y,0);
    	}
    	for(int i = 1 ; i <= n ; i++)
    		add(n+1,i,1);
    	cout << spfa() << endl;
    	return 0;
    }
    
    • 1
      @ 2023-7-24 20:10:39
      #include <bits/stdc++.h>
      using namespace std;
      #define int long long //不开long long见祖宗
      const int N=1e6+10;
      int n,m,head[N],ne[N],w[N],to[N],id,dis[N],vis[N],cnt[N];
      inline void add(int x,int y,int z){
      	to[++id]=y,w[id]=z,ne[id]=head[x],head[x]=id;
      }
      int spfa(){
      	memset(dis,-0x3f,sizeof(dis));
      	dis[n+1]=0,vis[n+1]=1,cnt[n+1]=1;
      	stack<int> q;
      	q.push(n+1);
      	while(!q.empty()){
      		int t=q.top();
      		q.pop();
      		vis[t]=0;
      		for(int i=head[t];i;i=ne[i]){
      			int v=to[i];
      			if(dis[v]<dis[t]+w[i]){
      				dis[v]=dis[t]+w[i];
      				if(!vis[v]){
      					q.push(v),vis[v]=1;
      					if(++cnt[v]>=n) return -1;
      				}
      			}
      		}
      	}
      	int sum=0;
      	for(int i=1;i<=n+1;i++){
      		sum+=dis[i];
      	}
      	return sum;
      }
      signed main(){
      	cin>>n>>m;
      	for(int i=0,x,y,z;i<m;i++){
      		cin>>z>>x>>y;
      		if(z==1){
      			add(x,y,0),add(y,x,0);
      		}else if(z==2){
      			add(x,y,1);
      		}else if(z==3){
      			add(y,x,0);
      		}else if(z==4){
      			add(y,x,1);
      		}else if(z==5){
      			add(x,y,0);		
      		} 
      	}
      	for(int i=1;i<=n;i++) add(n+1,i,1);
      	cout<<spfa();
      }
      
      • 0
        @ 2021-11-27 16:14:16
        /*****************************************
        备注:
        ******************************************/
        #include <queue>
        #include <math.h>
        #include <stack>
        #include <stdio.h>
        #include <iostream>
        #include <vector>
        #include <iomanip>
        #include <string.h>
        #include <algorithm>
        using namespace std;
        #define LL long long
        const int N = 2e6 + 10;
        const int INF = 0x3f3f3f3f;
        LL head[N] , to[N],w[N],ne[N],idx=0;
        LL vis[N] , dis[N] ,num[N];
        inline void add(int x,int y , int z)
        {
        	to[++idx] = y;
        	w[idx] = z;
        	ne[idx] = head[x];
        	head[x] = idx;
        }
        LL n , k;
        LL spfa()
        {
        	memset(dis,-0x3f, sizeof dis);
        	stack<int> p;
        	dis[n+1] = 0;
        	vis[n+1] = 1;
        	num[n+1] = 1;
        	p.push(n+1);
        	while( !p.empty())
        	{
        		int t = p.top();
        		p.pop();
        		vis[t] = 0;
        		for(int i = head[t] ; i ; i = ne[i])
        		{
        			int u = to[i];
        			if(dis[u] < dis[t] + w[i])
        			{
        				dis[u] = dis[t] + w[i];
        				if(!vis[u]) 
        				{
        					p.push(u);
        					vis[u] = 1;
        					if(++num[u] >= n) 
        						return -1;
        				}
        			}
        		}
        	}
        	LL sum = 0;
        	for(int i = 1 ; i <= n ; i++)
        		sum += dis[i];
        	return sum;
        }
        int main()
        {
        	cin >> n >> k;
        	for(int i = 0 ; i < k ; i++)
        	{
        		int z,x,y;
        		scanf("%d%d%d",&z,&x,&y);
        		if(z == 1)
        			add (x,y,0),add (y,x,0);
        		else if ( z == 2)
        			add(x,y,1);
        		else if( z == 3)
        			add(y,x,0);
        		else if(z == 4)
        			add(y,x,1);
        		else if(z ==5)
        			add(x,y,0);
        	}
        	for(int i = 1 ; i <= n ; i++)
        		add(n+1,i,1);
        	cout << spfa() << endl;
        	return 0;
        }
        
        
        
        
        
        
        
        • 1

        信息

        ID
        422
        时间
        1000ms
        内存
        256MiB
        难度
        7
        标签
        递交数
        163
        已通过
        42
        上传者