Topic linking :http://acm.hdu.edu.cn/showproblem.php?pid=5695

The question : Chinese questions , Don't explain

Answer key : Reverse the topological dictionary order

 #include<cstdio>
#include<string>
#include<set>
#include<vector>
#include<queue>
#include<functional>
using namespace std;
#define MAX 100010
int InDeg[MAX];
int n, m, Count;
int Ans[MAX];
vector<int> v[MAX];
void TopoSort()
{
priority_queue<int> PQ;
for(int i=n; i>=; i--) // Find out if the degree of penetration is 0 And put it in the priority queue
if(InDeg[i]==) PQ.push(i); while(!PQ.empty()) //BFS
{
int Tmp = PQ.top();
PQ.pop();
Ans[Count++] = Tmp;
for(int i=; i<v[Tmp].size(); i++)
{
InDeg[v[Tmp][i]]--;
if(InDeg[v[Tmp][i]]==) PQ.push(v[Tmp][i]);
}
}
} int main()
{
int x, y,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m); for(int i=;i<=n;i++)v[i].clear(),InDeg[i]=;
Count = ;
for(int i=; i<m; i++)
{
scanf("%d%d",&x,&y);
InDeg[y]++;
v[x].push_back(y);
}
TopoSort();
int min=;
long long an=;
for(int i=; i<Count; i++){
min=min>Ans[i]?Ans[i]:min;
an+=min;
}
printf("%I64d\n",an);
}
}

hdu_5695_Gym Class( A topological sort ) More articles about

  1. Algorithm and data structure ( 7、 ... and ) AOV Topological ordering of nets

    The content of today's blog is still related to pictures , The topic of today's blog is about topological ordering . Topological ordering is based on AOV Netted , About AOV The concept of the net , I would like to quote the following sentence to introduce : AOV network : In modern management , People often use digraph to describe and analyze the plan of a project ...

  2. Applications of directed acyclic graphs —AOV network and A topological sort

    Directed acyclic graph : Acyclic digraphs , abbreviation DAG (Directed Acycline Graph) chart . The spanning tree of a directed graph is a directed tree , Some strongly connected components of an unconnected digraph generate some directed trees , These digraphs form forests ...

  3. 【BZOJ-2938】 Viruses Trie chart + A topological sort

    2938: [Poi2000] Viruses Time Limit: 1 Sec  Memory Limit: 128 MBSubmit: 609  Solved: 318[Submit][Status][Di ...

  4. BZOJ1565 [NOI2009] Plants vs. zombies ( A topological sort + Maximum weighted closed subgraph )

    subject Source http://www.lydsy.com/JudgeOnline/problem.php?id=1565 Description Input Output Contains only one integer , Can be said ...

  5. chart —— A topological sort (uva10305)

    John has n tasks to do. Unfortunately, the tasks are not independent and the execution of one task i ...

  6. Java Sorting algorithm —— A topological sort

    package graph; import java.util.LinkedList; import java.util.Queue; import thinkinjava.net.mindview. ...

  7. poj 3687( A topological sort )

    http://poj.org/problem?id=3687 The question : There are some balls, they all have their own weight , And the weight of each ball is different , Now? , To label these balls . If there's no limit to which of these balls is lighter than which , So the default ...

  8. A topological sort - Union checking set - Rank of Tetris

    Description since Lele Developed Rating System , His Tetris Career is even more powerful , Soon he pushed the game all over the world . In order to better meet the preferences of those fans ,Lele Another new idea came up : He will make a global ...

  9. *HDU1285 A topological sort

    Determine the place in the competition Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Subm ...

Random recommendation

  1. Request how to enter ASP.NET MVC frame

    One . Preface about WebForm Development , A request is usually one with .aspx At the end of the url, Corresponding to a physical file , From a code point of view, it's actually a control (Page). And in the MVC in , A request corresponds to a Controller Inside Ac ...

  2. I'll teach you how to use nodejs+SQL Server2012 Add, delete, and check

    1. development tool WebStorm 10.0.4 2. open WebStorm 10.0.4 New projects :

  3. eliminate Xcode Cache and archive files

    XCode4.2    finder Find   /Users/Library/Developer/Xcode    ( notes :Library Repository is a hidden folder ) There are DerivedData and Snaps ...

  4. Add dynamic libraries to VC In the program

    Application usage DLL There are two ways : One is implicit linking , The other is explicit linking . In the use of DLL Before you know DLL Structure information of functions in .Visual C++6.0 stay VC\bin A directory named Dumpbin.ex ...

  5. php essays 11-Thinkphp Common system configuration

    Thinkphp Common configuration   CHECK_FILE_CASE -- windows Strict case checking under the environment . /* Project setting */     'APP_DEBUG'    => false, // ...

  6. golang in string and int Type conversion

    Sum up golang String and various int Conversion between types : string Turn into int: int, err := strconv.Atoi(string)string Turn into int64: int64, e ...

  7. Android Memory optimization ( Four )LeakCanary The use of,

    LeakCanary It's testing App Memory leak tools , The memory leak is Android Common problems in development , The stability of the application is reduced . LeakCanary The mechanism is as follows : RefWatcher.watch() We'll monitor ...

  8. cocos2d-x Drawing graphics

    Reprint please indicate the source :http://blog.csdn.net/oyangyufu/article/details/25841727 Draw a graph, for example :   Program code : You need to define the parent virtual function again draw() ...

  9. spring boot+mybatis+generator Generate domain Case problem

    There was a problem before , use generator Generate the database corresponding to domain, It used to be good , That day it suddenly came into being domain All lowercase , Because it's uppercase in my database , Later a solution was found , <table tableNa ...

  10. Django The components of --auth Components

    Catalog Auth What is a module auth Module common methods Extend default auth_user surface 1 Django The user authentication module comes with , Can quickly achieve login , Cancellation , Change Password ... 2 Expand auth surface , Need to inherit Abstrac ...