任务调度

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
struct node{
    string name;
    vector<string> sons;
    int number;
    
    bool operator < (const node& A) const
    {
        if(this->number != A.number)
        return this->number > A.number;
        else
        return this->name > A.name;
    }
};
vector<node> v;
map<string, node> mp;
vector<string> vs;
void split(string s)
{
    string t = "";
    bool isFirst = 1;
    vs.clear();
    for(int i = 0 ;i<s.length();i++)
    {
        if(s[i] == '(' || s[i] == ')' || s[i] == ',')
        {
            if(t == "NULL")
            {
                break;
            }
            vs.push_back(t);
            t = "";
            continue;
        }
        t += s[i];
    }
}
int main()
{
    int n;
    while(cin >> n)
    {
        mp.clear();
        v.clear();
        string s; 
        for(int i = 0 ; i<n;i++)
        {
            cin >> s;
            split(s);
            node t;
            t.name = vs[0];
            for(int j = 1;j<vs.size();j++)
            {
                t.sons.push_back(vs[j]);
            }
            t.number = 0;
            mp[t.name] = t;
            v.push_back(t);
        }
        for(int i = 0 ;i<v.size();i++)
        {
            node t = v[i];
            for(int j = 0 ; j<t.sons.size();j++)
            {
                mp[t.sons[j]].number++;
            }
        }
        priority_queue<node, vector<node> > q;
        for(int i = 0 ;i<v.size();i++)
        {
            q.push(v[i]);
        }
        while(!q.empty())
        {
            node t = q.top();
            q.pop();
            for(int i = 0 ;i<t.sons.size();i++)
            {
                mp[t.sons[i]].number--;
            }
            cout << t.name ;
            if(q.empty())
            cout << endl;
            else
            cout << " ";
        }
    } 
    return 0;
}

/*拓扑排序+最小堆*/
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#define N 100000
using namespace std;

int inDegree[N];
vector<int> M[N];//M[i]表示,i为M[i]下面所有结点相连的边的弧尾
priority_queue<int,vector<int>,greater<int>> Q;//构建最小堆，用于每次取出编号最小的任务

int getNo(string task){//获得任务的编号
    int ans=0;
    int c=1;
    int len = task.size();
    for(int i =len-1;i>=0;i--){
        if('0'<=task[i]&&task[i]<='9'){
            ans=ans+(task[i]-'0')*c;
        }
        else{
            break;
        }
        c*=10;
    }
    return ans;

}

int main()
{
    string str,substring;
    int n,no,pos;
    while(cin>>n){
        for(int i=0;i<n;i++){
            inDegree[i]=0;//初始化入度均为0
            M[i].clear();//清空邻接链表
        }
        for(int i=0;i<n;i++){
            cin>>str;
            pos=0;//起始搜索位置
            str.replace(str.find("("),1,",");
            str.replace(str.find(")"),1,",");
            while(1){//提取任务i的后续任务，并将其存储到任务i对应的链表当中
                pos = str.find(",",pos+1);//找到第一个逗号的位置
                if(str.find(",",pos+1)==string::npos)//如果后面还存在逗号
                    break;
                else{//得到所有后续任务的编号
                    substring = str.substr(pos+1,str.find(",",pos+1)-pos-1);//获取目标字符串
                    if(substring=="NULL")continue;
                    M[i].push_back(getNo(substring));//构建有向图
                }
            }
        }

        //开始进行拓扑排序
        for(int i=0;i<n;i++){
            if(inDegree[i]==0)
                Q.push(i);
        }
        while(!Q.empty()){
            int node = Q.top();
            Q.pop();
            cout<<"Task"<<node<<" ";
            for(int i=0;i<M[node].size();i++){
                inDegree[M[node][i]]--;
                if(inDegree[M[node][i]]==0)//如果上述操作产生了新的入度为0的结点，则将其插入最小堆当中
                    Q.push(M[node][i]);
            }

        }
        cout<<endl;

    }
    return 0;
}
/*
4
Task0(Task1,Task2)
Task1(Task3)
Task2(NULL)
Task3(NULL)
*/

	



	

#include<cstdio>
#include<iostream>
#include<string>
#include<queue>
#include<vector>
#include<map>
using namespace std;

struct node{                //定义优先队列节点及其优先法则
    string task;
    vector<string> sons;
    int sons_number;    //节点入度（忽略这个命名LOL，懒得改了）
    friend bool operator < (const node &A,const node &B ){
        if(A.sons_number!=B.sons_number)
            return A.sons_number > B.sons_number;    //入度越小优先级越高
        else
            return A.task > B.task;    //入度相同，按字典序排列
    }
};

priority_queue<node> q;    //定义优先队列
map<string,node> mp;    //用map记录每一个任务节点以便修改入度
string str;

int main(){
    int n;
    cin>>n;
    getchar();    //注意下面要使用getline()；所以这里要读掉回车，
    for(int i=0;i<n;i++){   
        getline(cin,str);        //逐行读入并处理
        int j=0;
        while(str[j]!='(') j++;
        string Task=str.substr(0,j);        //读取前序任务
        if(mp.find(Task)==mp.end()){        //该任务节点未建立则新建节点
            node Node;
            Node.sons_number=0;
            Node.task = Task;
            mp[Task] = Node ;
        }
        while(str[j]!=')'){        //处理后序任务节点的入度
            j++;
            int temp=j;
            while(str[j]!=','&&str[j]!=')') j++;
            if(str.substr(temp,(j-temp))!="NULL"){
                mp[Task].sons.push_back(str.substr(temp,(j-temp)));
                if(mp.find(str.substr(temp,(j-temp)))==mp.end()){//后序任务节点未建立则建立
                    node Node;
                    Node.task = str.substr(temp,(j-temp));
                    Node.sons_number=1;
                    mp[str.substr(temp,(j-temp))]=Node;
                }else{
                    mp[str.substr(temp,(j-temp))].sons_number++;
                }
            }
        }
        q.push(mp[Task]);
        
    }
    for(int i=0;i<n;i++){
        cout<<q.top().task<<' ';
        node Node=q.top();
        q.pop();
        for(int i=0;i<Node.sons.size();i++){
            mp[Node.sons[i]].sons_number--;
        }
    }
}

#include<iostream>
(720)#include<queue>
#include<algorithm>
(831)#include<vector>
using namespace std;
int n;
bool vist[100000]= {false};
vector<int> vt[100000];
void bfs() {
	queue<int> q;
	q.push(0);
	vist[0]=true;
	while(!q.empty()) {
		int t=q.front();
		q.pop();
		printf("Task%d ",t);
		for(int i=0; i<vt[t].size(); i++) {
			if(vist[vt[t][i]]==false) {
				q.push(vt[t][i]);
				vist[vt[t][i]]=true;
			}
		}
	}
}
int main() {
	cin>>n;
	getchar();
	map<string,int> sti;
	map<int,string> its;
	string temp,t,org="Task";
	for(int i=0,pos,pre; i<n; i++) {
		getline(cin,temp);
		t=temp.substr(0,5);
		pre=t[4]-'0';
		pos=6;
		while(1) {
			pos=temp.find(org,pos);
			if(pos==-1) break;
			t=temp.substr(pos,5);
			pos++;
			vt[pre].push_back(t[4]-'0');
		}
	}
	bfs();
}

人生苦短

res = []
for _ in range(int(input())):
    task = input()[:-1].replace('NULL', 'u').split('(')  #-1去掉右括号,把NULL替换成u（比'Task'大就好），排序会靠后
    res.append([task[0], sorted(task[1].split(','))])   #将后序任务也进行排序
res.sort(key=lambda x: (x[1], x[0]))           #以后序任务为首要，再以前序任务为次要排序
print(" ".join(i[0] for i in res))

#include<stdio.h>//直接排序去掉括号内容即可
#include<string.h>
int main()
{
    int n,i,j;
    char a[1000][1000],b[1000];
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%s",a[i]);
        for(j=0;j<strlen(a[i]);j++)
            if(a[i][j]=='(')
                a[i][j]='\0';
    }
    for(i=0;i<n-1;i++)//冒泡
        for(j=0;j<n-1-i;j++)
            if(strcmp(a[j],a[j+1])>0)
            {//交换
               strcpy(b,a[j]);strcpy(a[j],a[j+1]);strcpy(a[j+1],b); 
            }
    for(i=0;i<n;i++)
        printf("%s ",a[i]);
}

#include <queue>//不需要优先队列！！！普通的一个拓扑排序而已，感觉有好多人写的太复杂了
#include <iostream>
#include <cstring>
using namespace std;
int arr[1000][1000], inde[1000], n;
void topology()
{
    queue<int> q;
    for (int j = 0; j < n; j++)
    {
        if (inde[j] == 0)
        {
            q.push(j);
        }
    }
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        printf("Task%d ", p);
        for (int j = 0; j < n; j++)
        {
            if (arr[p][j] != 0)
            {
                if ((--inde[j]) == 0)
                    q.push(j);
            }
        }
    }
    printf("\n");
}
int main()
{
    while (cin >> n)
    {
        getchar();
        string s;
        memset(arr, 0, sizeof(arr));
        memset(inde, 0, sizeof(inde));
        for (int i = 0; i < n; i++)
        {
            getline(cin, s);
            int from = s[4] - '0', to;
            if (s[6] == 'N')
                continue;
            else
            {
                for (int j = 10; j < (int)s.size(); j += 6)
                {
                    to = s[j] - '0';
                    arr[from][to] = 1;
                    inde[to]++;
                }
            }
        }
        topology();
    }
    system("pause");
    return 0;
}

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <string>
using namespace std;
const int MAX = 10001;
vector<int> graph[MAX];
int indegree[MAX];
vector<int> TopologicalSort(int n){
    priority_queue<int, vector<int>, greater<int>> myqueue; //小的在前
    for(int i=0; i<n; ++i){
        if(indegree[i] == 0) myqueue.push(i);   //从0开始
    }
    vector<int> ans;      //记录序列
    while(!myqueue.empty()){
        int u = myqueue.top();
        myqueue.pop();
        ans.push_back(u);
        for(int i=0; i<graph[u].size(); ++i){
            int v = graph[u][i];
            indegree[v]--;
            if(indegree[v] == 0) myqueue.push(v);
        }
    }
    return ans;
}
int main(){
    int n;
    while(cin >> n){
        memset(graph, 0, sizeof(graph));
        fill(indegree, indegree+n, 0);
        int from, to;
        string str;
        for(int i=0; i<n; ++i){
            cin >> str;
            string temp;
            int num;
            for(int j=6; j<str.size()-1; ++j){
                if(str[6]=='N') break;
                if(str[j]>='0' && str[j]<='9'){
                    temp.push_back(str[j]);
                    if(str[j+1]==',' || str[j+1]==')'){
                        num = stoi(temp);
                        graph[str[4]-'0'].push_back(num);
                        indegree[num]++;
                        temp.clear();
                    }
                }
            }
        }
        vector<int> res = TopologicalSort(n);
        for(int i=0; i<res.size(); ++i){
            cout << "Task" << res[i] << ' ';
        }
        cout << endl;
    }
}

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<algorithm>
#define N 100005
using namespace std;
int n;
int indegree[N];//表示入度
vector<int> graph[N];//用来表示图的邻接表
vector<int> v1;
struct node {
    int n;//表示结点序号
    int degree;//表示度
};
priority_queue<node> pq;
bool operator < (node lhs, node rhs) {
    return lhs.n > rhs.n;
}
void topology(string str) {
    int flag = 0;
    int a = str[4] - '0';
    if (str[6] != 'N') {
        for (int j = 10; j < str.size(); j++) {
            if (isdigit(str[j])) {
                graph[a].push_back(str[j] -'0'); //将某节点的后继结点放入邻接表中
                indegree[str[j] -'0']++; //该结点是某个结点的后继结点，该结点的入度+1
            }
        }
    }
}
int main() { //拓扑排序
    //int n;
    vector<string> vs;
    while (cin >> n) {
        for (int i = 0; i < n; i++) {
            string str;
            cin >> str;
            topology(str);
        }
        for (int i = 0; i < n; i++) { //将度为零的结点入度
            node no;
            if (indegree[i] == 0) {
                no.degree = 0;
                no.n = i;
                pq.push(no);
            }
        }
        //sort(vz.begin(),vz.end());
        while (!pq.empty()) { //将入读为0的结点出队，并且将遍历其后继结点其后继结点的入度-1，
            int t = pq.top().n;
            pq.pop();
            cout << "Task" << t << " ";
            for (int i = 0; i < graph[t].size(); i++) {
                indegree[graph[t][i]]--;//对应结点入读-1
                if (indegree[graph[t][i]] == 0) {
                    node no;
                    no.degree = 0;
                    no.n = graph[t][i];
                    pq.push(no);
                }
            }

        }

    }

}

#include "bits/stdc++.h"
using namespace std;
inline int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (!(c <= '9' && c >= '0')) {
        if (c == '-') {
            f = -1;
        }
        c = getchar();
    }
    while (c <= '9' && c >= '0') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}

int head[100005],cnt,n;
unordered_map<int,int>din;
vector<int>tp;
struct Edge{
    int to,next;
}edge[100000*4];
void addedge(int u,int v){
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}
bool toposort(){
    priority_queue<int,vector<int>,greater<int>>q;
    for(auto t:din){
        if(t.second==0){
            q.push(t.first);
            //cout<<t.first<<endl;
        }
    }
    while (!q.empty()){
        auto t=q.top();
        q.pop();
        tp.push_back(t);
        for(int i=head[t];i;i=edge[i].next){
            int v=edge[i].to;
            if(--din[v]==0){
                q.push(v);
            }
        }
    }
    return tp.size()==n;
}

int main() {
    n=read();
    for(int i=1;i<=n;i++){
        int u;
        scanf("Task%d",&u);
        din[u]=0;
        string str;
        getline(cin,str);
        int x=0,flag=0;//flag=1表示正在读数字
        for(int j=0;j<str.size();j++){
            if(str[j]<='9' && str[j]>='0'){
                flag=1;
                x=(x<<3)+(x<<1)+(str[j]^48);
            }else{
                if(flag==1){
                    //cout<<u<<" "<<x<<endl;
                    addedge(u,x);
                    din[x]++;
                    flag=0;
                }
                x=0;
            }
        }
    }
    if(toposort()){
        for(auto t:tp){
            cout<<"Task"<<t<<" ";
        }
    }else{
        //出现了环
        exit(0);
    }
    return 0;
}

#include"iostream"
#include"queue"
#include"map"
#include"string"
#include"vector"
using namespace std;

/* In degree table*/
map<string, int> inDegreeTab;
/* adjoin table*/
map<string, vector<string>> adjTab;
/* topological sorting*/
bool topologicalSorting(string &output){
	
	int num= 0;
	priority_queue<string, vector<string>, greater<string>> myQueue;
	// ls inDegreeTab
	for(map<string, int>:: iterator it= inDegreeTab.begin(); it!= inDegreeTab.end(); it++){
		if(it->second== 0){
			myQueue.push(it->first);
			num++;
		}
	}
	// bianli
	while(!myQueue.empty()){
		string task= myQueue.top();// pop
		myQueue.pop();
		output= output +" " +task;// add into load
		vector<string> v= adjTab[task];
		for(int i= 0; i< v.size(); i++){
			inDegreeTab[v[i]]--;
			if(inDegreeTab[v[i]]== 0){
				myQueue.push(v[i]);
				num++;
			}
		}
	}
	// ret
	if(output.length()>0){output= output.substr(1);}
	return num== inDegreeTab.size();
}
int main(){
	
	int n;
	while(cin>> n){
		// init inDegreeTab、adjTab 
		inDegreeTab.clear();
		adjTab.clear();
		// input 
		string ipt;
		for(int i= 0; i< n; i++){
			cin>> ipt;// task0
			string t1= ipt.substr(0, ipt.find('('));
			ipt= ipt.substr(ipt.find('('));// (task1,task2)
			ipt= ipt.substr(1, ipt.length()-2); // remove () >> task1,task2
			ipt= ipt+ ",";// task1,task2,
			// init degree tab
			if(inDegreeTab.count(t1)== 0){
				inDegreeTab[t1]= 0;// no find insert
			}
			if(adjTab.count(t1)== 0){
				adjTab[t1]=vector<string>(0);// ji ling ghost
			}
			while(ipt!=""){
				string t= ipt.substr(0, ipt.find(',')+ 1);// task1,
				t= t.substr(0, t.length()- 1);// task1
				ipt= ipt.substr(ipt.find(',')+ 1);//task2,..,
				if(t!="NULL"){// init adjoin table and indegree tab
					adjTab[t1].push_back(t);
					inDegreeTab[t]++;
				}
			}
		}
		// topologicalSorting
		string opt;
		if(topologicalSorting(opt)){
			cout<< opt<<endl;
		}
	}
}

图采用邻接表法，代码可复用性强

#include<iostream>
#include<unistd.h>
#include<vector>
#include<map>
using namespace std;

struct Node{
    Node* next;
    string name;
    Node(string task_name):name(task_name),next(nullptr){}
    void insert(string task_name){
        if(task_name=="NULL") return;
        Node* n = new Node(task_name);
        n->next = this->next;
        this->next = n;

    }
    bool is_in_next_list(string task_name){
        Node* h = next;  
        while(h!=nullptr){
            if(h->name==task_name){
                return true;
            }
        }
        return false;
    }
    void erase(string task_name){
        Node* h = this;
        while(h->next!=nullptr){
            if(h->next->name==task_name){
                Node* temp=h->next;
                h->next = temp->next;
                delete temp;
                return;
            }
            h=h->next;
        }
    }
};

struct Graph{
    Graph(){} 
    ~Graph(){
        for(int i=0;i<m_edge.size();i++){
            Node* head = m_edge[i];
            while(head!=nullptr){
                Node* temp = head->next;  
                delete head;
                head=temp;
            }
        }
    }
    void insert(Node* n){
        auto it = m.find(n->name);
        if(it==m.end()){
            m_edge.push_back(n);
            m[n->name]=n;
            return;
        }
        Node* edgeNode = it->second; 
        n=n->next;
        while(n!=nullptr){
            Node* temp = n->next;
            if(edgeNode->is_in_next_list(n->name)){
                delete n;
                n=temp;
                continue;
            }
            //头插法
            n->next = edgeNode->next;
            edgeNode->next=n;
            n=temp;
        }
    }
    bool hasPre(string task_name){
        for(int i=0;i<m_edge.size();i++){
            Node* h = m_edge[i]->next;
            while(h!=nullptr){
                if(h->name==task_name) return true; 
                h=h->next;
            }
        }
        return false;
    }
    void erase(string task_name){
        auto it = m.find(task_name);
        if(it!=m.end()) m.erase(it);
        //遍历每个边表节点
        vector<Node*>::iterator iter;
        int flag=0;
        for(auto it=m_edge.begin();it!=m_edge.end();it++){
            if((*it)->name==task_name){
                delete *it;
                flag=1;
                iter = it;
                continue;
            }
            Node* edge_node = *it;
            edge_node->erase(task_name);
        }
        if(flag==1) m_edge.erase(iter);
    }
    void topological_sort(){
        for(int i=0;i<m_edge.size();i++){
            string name = m_edge[i]->name;
            if(hasPre(name)) continue;;
            cout<<name<<" ";
            erase(name);
            break;
        } 
        if(m_edge.size()==0){cout<<endl;return;}
        topological_sort();
    }
private:
    vector<Node*> m_edge;       //边表节点
    map<string,Node*> m;
};

string get_next_task(const string& input,int& start){
    for(int i=start;i<input.size();i++){
        if(input[i]=='N'){
            start=i+4;
            return input.substr(i,4);
        }
        if(input[i]=='T'){
            start=i+5;
            return input.substr(i,5);
        }
    } 
    return "";
}

int main(){
    int n;
    string input;
    cin>>n;
    Graph g;
    while(n--){
        cin>>input;
        Node* edgeNode = new Node(input.substr(0,5));
        int start=6;
        string task_name;
        while((task_name = get_next_task(input,start))!=""){
            edgeNode->insert(task_name);
        }
        g.insert(edgeNode);
    }

    g.topological_sort();
    return 0;
}

一开始一度以为这道题要用拓扑排序求解，以至于搞了半天入度出度表。。结果只要把后续任务优先级简单加一就行了。

这道题的题设并不严谨，它没有说明输入的任务也是按字典序排序的，优先级简单加一仅适用于任务序号依次增加的情况，如图所示：

#include <bits/stdc++.h>

using namespace std;

struct task{
    int tno;
    int priority;
    task(){
        tno = 0;
        priority = 0;
    }
    friend bool operator < (const task &t1, const task &t2){
        if(t1.priority!=t2.priority)
            return t1.priority>t2.priority;
        else
            return t1.tno > t2.tno;
    }
}taskList[100010];

bool isLeagle(char c){
    if((c>='a'&&c<='z')||(c>='A'&&c<='Z')||(c>='0'&&c<='9'))
        return true;
    else return false;
}

int main() {
    int n;
    while(scanf("%d" ,&n)!=EOF){
        priority_queue<task> q;
        for(int i=0; i<n; i++){
            string str;
            cin>>str;
            for(int j=0; j<str.size(); j++){
                if(!isLeagle(str[j]))
                    str[j] = ' ';
            }
            stringstream Str;
            Str.str(str);
            string tok;
            getline(Str, tok, ' ');
            int t = tok[4] - '0';
            taskList[t].tno = t;
            while(getline(Str, tok, ' ')){
                if(tok!="NULL")
                    taskList[tok[4] - '0'].priority = taskList[t].priority+1;
            }
        }
        for(int i=0; i<n; i++){
            q.push(taskList[i]);
        }
        while(q.size()>=1){
			task t=q.top();
			q.pop();
			printf("Task%d ",t.tno);
		}
        printf("\n");
    }
	return 0;
}

/*
字符串处理+拓扑排序（使用优先队列使其按字典排序）
按题意，图中无环
*/
#include <iostream>
#include <vector>
#include <string>
#include <iomanip>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
struct Node {
	int indgree;
	vector<string> sub_tasks;
	string name;

	bool operator < (const Node& n) const {
		if (indgree != n.indgree) return indgree > n.indgree;
		else return name > n.name;
	}
};
map<string, Node> graph;
int main() {
	int n;
	while (cin >> n) {
		string tasks;
		while (n--) {
			cin >> tasks;
			int left = tasks.find('(');
			int right = tasks.find(')');
			string priority = tasks.substr(0, left);
			string sub_task = tasks.substr(left + 1, right - left - 1);
			Node node;
			node.name = priority;
			node.indgree = 0;
			node.sub_tasks.clear();
			if (sub_task != "NULL") {
				string sub;
				for (int i = 0; i < sub_task.size(); i++) {
					if (sub_task[i] == ',') {
						node.sub_tasks.push_back(sub);
						sub.clear();
						continue;
					}
					sub += sub_task[i];
				}
				node.sub_tasks.push_back(sub);
			}
			graph[node.name] = node;
		}
		for (auto i = graph.begin(); i != graph.end(); i++) {
			for (auto j : i->second.sub_tasks) {
				graph[j].indgree++;
			}
		}
		priority_queue<Node> q;
		for (auto i = graph.begin(); i != graph.end(); i++) {
			if(i->second.indgree==0)
				q.push(i->second);
		}
		int count = 0;
		while (!q.empty()) {
			Node node = q.top();
			q.pop();
			count++;
			for (auto i : node.sub_tasks) {
				graph[i].indgree--;
				if (graph[i].indgree == 0)
					q.push(graph[i]);
			}
			cout << node.name;
			if (q.empty())cout << endl;
			else cout << " ";
		}
		//if (count == graph.size())cout << "YES" << endl;
	}


	return 0;
}