I think that this depends largely on the composition of your team - how well do you know F#?
I feel like I am able to develop almost anything more quickly in F# than C#. In particular, highly algorithmic programs are often more concise and readable when expressed in F# thanks to type inference. However, if you don't have much experience with F# there is a significant learning curve, which means that you may be better off sticking to C# if you already know that language well.
C#'s support for doing operations in parallel is roughly equivalent to F#'s, particularly if your task doesn't require accessing any shared mutable state (which seems to be the case for your task). If I understand your problem correctly, you'd just like to run the same operation on multiple graphs at the same time, which ought to be quite easy in either language. If you were trying to parallelize the max-flow algorithm itself, then F# might be a bit easier due to its stronger support for immutable data types. Where F# really beats C# is in doing asynchronous operations, but that seems less relevant here.