题目要求不能通过相同的点，限制点，和蜥蜴那个题类似，将每个点拆成两个点，中间连一条边，因为每个点只能通过一次，所以边的流量为1。 因为起点和汇点不算十字路口，所以不用拆，在与1号点直接相连的点和1号点之间连一条流量为1的边，与n号点相连的点一样如此处理，然后用最小费用最大流就可以了。最大流即为天数，最小费用即为总路程。 需要注意的问题是构建cost的反向边。
代码
#include<iostream> #include<cstring> #include<string> #include<cstdio> #include<algorithm> #include<queue> #include<vector> #define INF 2139062143 using namespace std; int n,m; int pre[409],f[409]; int cost[409][409],cap[409][409]; int mflow=0,mcost=0; int flow[409],dis[409]; int bfs(int s,int t) { queue <int> q; while(!q.empty()) q.pop(); memset(pre,-1,sizeof(pre)); memset(dis,127,sizeof(dis)); memset(f,0,sizeof(f)); q.push(s); pre[s]=0; flow[s]=INF; dis[s]=0; f[s]=1; while(!q.empty()) { int k=q.front(); q.pop(); f[k]=0; for(int i=1;i<2*n;i++) { if(cap[k][i]>0&&dis[i]>dis[k]+cost[k][i]) { dis[i]=dis[k]+cost[k][i]; flow[i]=min(flow[k],cap[k][i]); pre[i]=k; if(!f[i]) q.push(i),f[i]=1; } } } if(pre[t]==-1) return -1; return flow[t]; } void maxflow(int s,int t) { int d; while(1) { d=bfs(s,t); if(d==-1) return; int k=t; while(k!=s) { cap[pre[k]][k]-=d; cap[k][pre[k]]+=d; k=pre[k]; } mflow+=d; mcost+=d*dis[t]; } return; } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); int cu; if(a==1) cu=1; else cu=a+n; cap[cu][b]=1; cost[cu][b]=c; cost[b][cu]=-c;//反向边 } for(int i=2;i<=n-1;i++) cap[i][i+n]=1; maxflow(1,n); printf("%d %d",mflow,mcost); return 0; }