容鄙人说一下，这是鄙人刷过最caodan的一个题，我就没见过这么刁钻的数据..
传入层的出度可以是0，但是，他依然可以传导，并且还应该被当做答案输出
第二，传入层一开始就是激发状态！并且不能减u 我就没见过这么caodan的
题目似乎也说了
意思是传入层根本没有j属于i,那么按这个推ci就是负数，也就无法传导，所以…就很离谱的不要减u才正确，关键是题目根本没有挑明。。
include <iostream>
include<vector>
include<queue>
using namespace std;
int ru[110];
int chu[110];
int f[110][110];
vector<int>v[110];
int c[110],u[110];
queue<int>q;
int main()
{
int n,m;
cin>>n>>m;
for(int i=1; i<=n; i++) { cin>>c[i]>>u[i];
}
for(int i=1; i<=m; i++) { int x,y,z; cin>>x>>y>>z;
f[x][y]=z;
v[x].push_back(y);
chu[x]++;
ru[y]++;
}
for(int i=1; i<=n; i++) { if(ru[i]="=0)" q.push(i); c[i]-="u[i];" } else while(!q.empty()) int now="q.front();" q.pop(); for(auto it:v[now]) ru[it]--; c[it]+="c[now]*f[now][it];" if(ru[it]="=0&&c[it]">0)
{
q.push(it);
}
}
}
int flag=0;
for(int i=1; i<=n; i++) { if(chu[i]="=0&&c[i]">0)
{
cout<<i<<" "<<c[i]<<endl; flag="1;" } if(!flag) { cout<<"null"; return 0; < code></i<<"></=n;></=n;></=m;></=n;></int></int></queue></vector></iostream>
把等级低的往等级高的连一条有向边即可，拓扑DP
#include <iostream>
include<algorithm>
include<cstring>
include<vector>
include<queue>
using namespace std;
typedef long long int ll;
int du[1010];
int st[1010];
bool book[1010];
bool edge[1010][1010];
vector<int>v[1010];
int ans[1010];
int dp[1010];
queue<int>q;
int main()
{
int n,m;
cin>>n>>m;
while(m--)
{
int t;
cin>>t;
for(int i=1; i<=t; i++) { cin>>st[i];
book[st[i]]=1;
}
for(int i=st[1]; i<=st[t]; i++) { if(!book[i]) for(int j="1;" j<="t;" j++) if(!edge[i][st[j]]) edge[i][st[j]]="1;" v[i].push_back(st[j]); du[st[j]]++; } memset(book,0,sizeof(book)); i="1;" i<="n;" if(!du[i]) q.push(i); dp[i]="1;" int ans="1;" while(!q.empty()) now="q.front();" q.pop(); for(auto it:v[now]) du[it]--; if(du[it]="=0)" q.push(it); if(!dp[it]) dp[it]="dp[now]+1;" else cout<<ans; return 0; < code></=st[t];></=t;></int></int></queue></vector></cstring></algorithm></iostream>
两种贪心方法，第一种是放进小根堆，把最小的先输出。但会被hack，例如
（5,2） （4,3） 输出 1 4 3 5 2 实际上应该是 1 5 2 4 3。
第二种就是放进大根堆，建立反图，倒着输出
(5,2) (4,3) -> (2,5) (3,4) -> 3 4 2 5 1 -> 1 5 2 4 3
这样就OK了
include <iostream>
include<algorithm>
include<cstring>
include<vector>
include<queue>
using namespace std;
typedef long long int ll;
vector<int>v[100000+10];
int du[100000+10];
priority_queue<int>q;
int ans[100000+10];
int main()
{
int t;
cin>>t;
while(t--)
{
int n,m,len;
cin>>n>>m;
while(!q.empty())
q.pop();
for(int i=1;i<=n;i++) { v[i].clear(); du[i]="0;" } for(int i="1;i<=m;i++)" int x,y; cin>>x>>y;
v[y].push_back(x);
du[x]++;
}
for(int i=1;i<=n;i++) { if(du[i]="=0)" q.push(i); } len="0;" while(!q.empty()) int now="q.top();" len++; ans[len]="now;" q.pop(); for(auto it:v[now]) du[it]--; if(!du[it]) q.push(it); if(len!="n)" cout<<"impossible!"<<endl; continue; for(int i="len;i">=1;i--)
{
cout<<ans[i]<<" "; } cout<<endl; return 0; < code></ans[i]<<"></=n;i++)></=n;i++)></int></int></queue></vector></cstring></algorithm></iostream>
基于迪杰斯特拉的BFS，为了能够拦截，必须上下左右连续建造墙，从第一整列，第n整行开始扩展，每次选取最小花费的点，只能上下左右移动，一旦到达第一行或者第m列，拦截成功。细节较多，要开ll
#include <queue>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
int nx[4]= {0,0,-1,1};
int ny[4]= {1,-1,0,0};
int n,m;
bool check(int x,int y)
{
return (x>=1&&x<=n&&y>=1&&y<=m); } ll mp[510][510], rem[510][510], inf="1e18,edge[510][510];" struct node { int x,y; cost; friend bool operator<(node a, b) return a.cost>b.cost;
}
};
priority_queue<node>q;
bool book[510][510];
int main ()
{
int t;
cin>>t>>n>>m;
while(t--)
{
for(int i=1; i<=n; i++) { for(int j="1;" j<="m;" j++) cin>>mp[i][j];
if(mp[i][j]==0)
mp[i][j]=-1;
else if(mp[i][j]==-1)
mp[i][j]=0;
rem[i][j]=inf;
}
}
memset(book,0,sizeof(book));
for(int i=1; i<=n; i++) { if(mp[i][1]="=-1)" continue; struct node now; now.x="i;" now.y="1;" now.cost="0;" rem[i][1]="0;" book[i][1]="1;" } else q.push(now); for(int i="1;" i<="m;" if(mp[n][i]="=-1)" rem[n][i]="0;" book[n][i]="1;" ll ans="-1;" while(!q.empty()) now="q.top();" q.pop(); if(now.x="=1||now.y==m)" break; i<4; int xx="now.x+nx[i];" yy="now.y+ny[i];" if(!check(xx,yy)) if(mp[xx][yy]="=-1)" if(rem[xx][yy]>now.cost+mp[xx][yy])
{
rem[xx][yy]=now.cost+mp[xx][yy];
struct node tail;
book[xx][yy]=1;
tail.x=xx;
tail.y=yy;
tail.cost=rem[xx][yy];
q.push(tail);
}
}
}
while(!q.empty())
q.pop();
cout<<ans<<endl; } < code></ans<<endl;></=n;></=n;></node></=m);></=n&&y></cstring></cstdio></algorithm></iostream></queue>
Original: https://blog.csdn.net/jisuanji2606414/article/details/126112038
Author: 秦小咩
Title: 图论刷题记录
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/659164/
转载文章受原作者版权保护。转载请注明原作者出处！