有正环才求不出最长路啊...还有最长路也是可以求的 是不是写萎了
by Mr_Spade @ 2018-11-06 09:11:07
@[黎曦の夜](/space/show?uid=76208) 可以的啊
```cpp
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define rei register int
using namespace std;
const int MAXN = 105, MAXM = 1005<<1;
const int INF = 1e9;
int n, s, t;
int P[MAXN][MAXN], Q[MAXN][MAXN];
int max_cost;
struct Edge
{
int next;
int u, v;
int data, cost;
}edge[MAXM];
int num_edge = 1;
int head[MAXN];
inline void make_edge(int u, int v, int data, int cost)
{
edge[++num_edge].next = head[u];
edge[num_edge].u = u;
edge[num_edge].v = v;
edge[num_edge].data = data;
edge[num_edge].cost = cost;
head[u] = num_edge;
return ;
}
int dis[MAXN];
queue<int> q;
bool vis[MAXN];
int pre[MAXN];
bool SPFA()
{
fill(dis,dis+MAXN,-INF);
memset(vis,0,sizeof(vis) );
memset(pre,0,sizeof(pre) );
q.push(s), dis[s] = 0, vis[s] = 1;
while(!q.empty() )
{
int u = q.front(); q.pop();
for(rei i=head[u];i>1;i=edge[i].next)
{
int v = edge[i].v;
if( edge[i].data && dis[u]+edge[i].cost>dis[v] )
{
dis[v] = dis[u] +edge[i].cost;
pre[v] = i;
if(!vis[v]) q.push(v), vis[v] = 1;
}
}
vis[u] = 0;
}
return dis[t]!=-INF;
}
void cost_flow()
{
int minn = INF;
while( SPFA() )
{
minn = INF;
for(rei i=pre[t];i>1;i=pre[ edge[i].u ]) minn = min(minn,edge[i].data);
for(rei i=pre[t];i>1;i=pre[ edge[i].u ])
{
max_cost += minn*edge[i].cost;
edge[i].data -= minn;
edge[i^1].data += minn;
}
}
return ;
}
int main()
{
scanf("%d",&n);
s = 1, t = 2*n+2;
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) scanf("%d",&P[i][j]);
for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) scanf("%d",&Q[i][j]);
for(int i=1;i<=n;++i)
{
make_edge(s,i+1,1,0), make_edge(i+1,s,0,0);
for(int j=1;j<=n;++j)
{
make_edge(i+1,j+1+n,1,P[i][j]*Q[j][i]), make_edge(j+1+n,i+1,0,-P[i][j]*Q[j][i]);
}
make_edge(i+1+n,t,1,0), make_edge(t,i+1+n,0,0);
}
cost_flow();
printf("%d",max_cost);
return 0;
}
```
by Md_Drew @ 2019-07-31 22:11:37
我也30分，不知道为什么
by 1261687299kid @ 2019-08-14 10:39:24