@[KK_lang](/user/548203) 等下我来看一眼,我在上课
by Infinite_Eternity @ 2023-01-13 19:39:13
@[Infinite_Eternity](/user/897776) 不急,谢
by KK_lang @ 2023-01-13 19:41:07
改到 80pts 了,WA#3,调的话看这版:
```cpp
#include<bits/stdc++.h>
using namespace std;
int n, m, c[110], u[110], f[110];
int inD[110], outD[110];
struct Edge
{
int pos, w;
Edge(int pos, int w) : pos(pos), w(w) {}
};
vector<Edge> From[110];
vector<Edge> To[110];
void TopoSort()
{
queue<int> q;
for (int i = 1; i <= n; i++)
if (inD[i] == 0) q.push(i);
while (!q.empty())
{
int fr = q.front();
q.pop();
if (c[fr]) f[fr] = c[fr];
else
{
for (int i = 0; i < From[fr].size(); i++)
if (f[From[fr][i].pos]) f[fr] += (From[fr][i].w * f[From[fr][i].pos]);
f[fr] -= u[fr];
}
for (int i = 0; i < To[fr].size(); i++)
if (--inD[To[fr][i].pos] == 0) q.push(To[fr][i].pos);
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> c[i] >> u[i];
for (int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
inD[v]++, outD[u]++;
From[v].push_back((Edge){u, w});
To[u].push_back((Edge){v, w});
}
TopoSort();
bool flag = false;
for (int i = 1; i <= n; i++)
if (!outD[i] && f[i] > 0)
{
cout << i << " " << f[i] << endl;
flag = true;
}
if (!flag) cout << "NULL" << endl;
return 0;
}
```
by KK_lang @ 2023-01-13 19:48:56
@[KK_lang](/user/548203) 急什么,我还有15分钟上完。
by Infinite_Eternity @ 2023-01-13 20:11:04
@[KK_lang](/user/548203)
```cpp
#include<bits/stdc++.h>
#define Inline __inline__ __attribute__((always_inline))
using namespace std;
template<typename T>
Inline void read(T &x){ x=0;register int f=1;register char c=getchar();while(c < '0' || c > '9'){if(c=='-')f=-1;c=getchar();}while(c >= '0' && c <= '9'){x=x*10+c-'0';c=getchar();}x*=f;}
template<typename T, typename ... Args>
Inline void read(T &x, Args &... y){ read(x);read(y...); }
int n,p;
int c[110],u[110],f[110];
int inD[110],outD[110];
struct edge
{
int v,w;
edge(int _v,int _w) : v(_v), w(_w) {}
};
vector<edge>E[110];
queue<int>q;
inline bool topsort()
{
int cnt=0;
for(int i=1; i<=n; ++i)
{
if(inD[i]==0) f[i]=1,q.push(i);
if(outD[i]==0) cnt++;
}
while(!q.empty())
{
int dist=q.front();
q.pop();
if(f[dist]==0) c[dist]-=u[dist];
if(c[dist]==0 && outD[dist]==0) cnt--;
for(int i=0; i<E[dist].size(); ++i)
{
int v=E[dist][i].v;
int w=E[dist][i].w;
inD[v]--;
if(inD[v]==0) q.push(v);
if(c[dist]>0) c[v]+=w*c[dist];
}
}
return cnt==0;
}
int main()
{
read(n,p);
for(int i=1; i<=n; ++i)
read(c[i],u[i]);
for(int i=1; i<=p; ++i)
{
int u,v,w;
read(u,v,w);
E[u].push_back(edge(v,w));
outD[u]++,inD[v]++;
}
if(topsort())
printf("NULL");
else
{
for(int i=1; i<=n; ++i)
if(outD[i]==0 && c[i]>0)
printf("%d %d\n",i,c[i]);
}
return 0;
}
```
by Infinite_Eternity @ 2023-01-13 20:53:02
@[Infinite_Eternity](/user/897776) 谢
by KK_lang @ 2023-01-13 21:01:27
~~不能发题解吧~~
by linjianju_xi @ 2023-11-04 08:25:53